【2018百度之星程序设计大赛资格赛】三原色图

三原色图

Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

Problem Description

度度熊有一张 n 个点 m 条边的无向图，所有点按照 1,2,⋯,n 1 , 2 , ⋯ , n 标号，每条边有一个正整数权值以及一种色光三原色红、绿、蓝之一的颜色。

现在度度熊想选出恰好 k 条边，满足只用这 k 条边之中的红色边和绿色边就能使 n 个点之间两两连通，或者只用这 k 条边之中的蓝色边和绿色边就能使 n 个点之间两两连通，这里两个点连通是指从一个点出发沿着边可以走到另一个点。

对于每个 k=1,2,⋯,m k = 1 , 2 , ⋯ , m ，你都需要帮度度熊计算选出恰好 k 条满足条件的边的权值之和的最小值。

Input

第一行包含一个正整数 T，表示有 T 组测试数据。

接下来依次描述 T 组测试数据。对于每组测试数据：

第一行包含两个整数 n 和 m，表示图的点数和边数。

接下来 m 行，每行包含三个整数 a,b,w和一个字符 c，表示有一条连接点 a 与点 b 的权值为 w、颜色为 c 的无向边。

保证 1≤T≤100 1 ≤ T ≤ 100 ， 1≤n,m≤100 1 ≤ n , m ≤ 100 ， 1≤a,b≤n 1 ≤ a , b ≤ n ， 1≤w≤1000 1 ≤ w ≤ 1000 ， c∈R,G,B c ∈ R , G , B ，这里 R,G,B 分别表示红色、绿色和蓝色。

Output

对于每组测试数据，先输出一行信息 “Case #x:”（不含引号），其中 x 表示这是第 x 组测试数据，接下来 m 行，每行包含一个整数，第 i 行的整数表示选出恰好 i 条满足条件的边的权值之和的最小值，如果不存在合法方案，输出 -1，行末不要有多余空格。

Sample Input

1

5 8

1 5 1 R

2 1 2 R

5 4 5 R

4 5 3 G

1 3 3 G

4 3 5 G

5 4 1 B

1 2 2 B

Sample Output

Case #1:

-1

-1

-1

9

10

12

17

22

solution

一道大水题。首先易得1~n-2的答案为-1，因为不管怎么取都不能做出一个最小生成树，然后将所有的边从小到大拍一遍序，然后分别做RG和BG的最小生成树，做完之后ans[n-1]的答案就是它们的最小值，然后从n-1~m每次加入一条当前最小生成树中未加入的最小的边再取个RG的BG的最小值就可以了。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1100
using namespace std;
int k,time,n,m,s,t,x[N],y[N],z[N],c[N],ans[N],f[N];
char color;
bool bz[N];
void qs(int l,int r){
    int i=l,j=r,m=z[l];
    while(i<=j){
        while(z[i]<m) i++;
        while(z[j]>m) j--;
        if(i<=j){
            x[]=x[i],x[i]=x[j],x[j]=x[];
            y[]=y[i],y[i]=y[j],y[j]=y[];
            c[]=c[i],c[i]=c[j],c[j]=c[];
            z[]=z[i],z[i]=z[j],z[j]=z[];
            i++,j--;
        }
    }
    if(l<j) qs(l,j);
    if(i<r) qs(i,r);
}
int get(int x){return f[x]==x?x:f[x]=get(f[x]);}
void kruskal(int k){
    memset(bz,,sizeof(bz));
    for(int i=;i<=n;i++) f[i]=i;
    s=t=;
    for(int i=;i<=m;i++) if(c[i]!=k){
        int fx=get(x[i]),fy=get(y[i]);
        if(fx!=fy){
            bz[i]=;
            f[fy]=fx;
            s+=z[i];
            t++;
            if(t==(n-)) break;
        }
    }
    if(t!=(n-)) return;
    if(ans[t]==-) ans[t]=s;
    else ans[t]=min(ans[t],s);
    for(int i=;i<=m;i++) if(!bz[i]){
        s+=z[i];
        t++;
        if(ans[t]==-) ans[t]=s;
        else ans[t]=min(ans[t],s);
    }

}
int main(){
    freopen("threecolorgraph.in","r",stdin);
    freopen("threecolorgraph.out","w",stdout);
    scanf("%d",&k);
    while(k--){
        printf("Case #%d:\n",++time);
        scanf("%d%d",&n,&m);
        memset(ans,,sizeof(ans));
        for(int i=;i<=m;i++){
            scanf("%d%d%d%c%c",&x[i],&y[i],&z[i],&color,&color);
            if(color=='R') c[i]=;
            if(color=='B') c[i]=;
            if(color=='G') c[i]=;
        }
        qs(,m);
        kruskal();
        kruskal();
        for(int i=;i<=m;i++) printf("%d\n",ans[i]);
    }
    return ;
}
           

打的很丑不要介意（^_^）

作者：zsjzliziyang

QQ:1634151125

转载及修改请注明

本文地址:https://blog.csdn.net/zsjzliziyang/article/details/81436049