题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6349
题目：
三原色图
Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 555 Accepted Submission(s): 186
Problem Description
度度熊有一张 n
个点 m
条边的无向图，所有点按照 1,2,⋯,n
标号，每条边有一个正整数权值以及一种色光三原色红、绿、蓝之一的颜色。
现在度度熊想选出恰好 k
条边，满足只用这 k
条边之中的红色边和绿色边就能使 n
个点之间两两连通，或者只用这 k
条边之中的蓝色边和绿色边就能使 n
个点之间两两连通，这里两个点连通是指从一个点出发沿着边可以走到另一个点。
对于每个 k=1,2,⋯,m
，你都需要帮度度熊计算选出恰好 k
条满足条件的边的权值之和的最小值。
Input
第一行包含一个正整数 T
，表示有 T
组测试数据。
接下来依次描述 T
组测试数据。对于每组测试数据：
第一行包含两个整数 n
和 m
，表示图的点数和边数。
接下来 m
行，每行包含三个整数 a,b,w
和一个字符 c
，表示有一条连接点 a
与点 b
的权值为 w
、颜色为 c
的无向边。
保证 1≤T≤100
，1≤n,m≤100
，1≤a,b≤n
，1≤w≤1000
，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
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
-1
-1
-1
9
10
12
17
22
解题思路：采用克鲁斯卡尔算法，构建最小生成树，边数小于n-1，无法构成所以答案为-1，如果可以构成的话，必定需要花费了n-1条边，对于剩下的n~m条边，参考大佬博客的做法，我们可以把它们放到一个从小到大排列的优先队列里，这样我们只要每次讲队首元素加入到答案，则出队即可。只需要跑两次克鲁斯卡尔，取答案的最小值就可以了。
这里也挺需要特别注意无法构成最小生成树的情况，答案全部为-1，我开始就在这WA了。
附上代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define maxn 105
#define inf 0x3f3f3f3f
priority_queue<int,vector<int>,greater<int> >que;
int n,m,par[maxn],rk[maxn],ans[maxn];
struct node{
int u,v,w,c;
bool operator<(const node &a)const
{ //按边的权值从小到大排
return w<a.w;
}
}edge[maxn]; //边数组
void init()
{ //初始化
for(int i=;i<=n;i++)
{
par[i]=i;
rk[i]=;
}
}
int find(int x)
{ //查找节点x所在树的根节点
if(x==par[x])
return x;
else //路径压缩
return par[x]=find(par[x]);
}
void unite(int x,int y)
{ //将两个不同集合的节点合并，两个集合变一个
int fx=find(x),fy=find(y);
if(rk[fx]<rk[fy])
par[fx]=fy;
else
{
par[fy]=fx;
if(rk[fx]==rk[fy])
rk[fx]++;
}
}
void kruskal(int c)
{
int cnt=,sum=; //cnt已选边的数目，sum为当前边权值之和
init();
while(!que.empty())
que.pop();
for(int i=;i<m;i++)
{
int u=edge[i].u,v=edge[i].v,col=edge[i].c;
if(find(u)!=find(v)&&col!=c&&cnt<=n-)
{
sum+=edge[i].w;
cnt++;
unite(u,v);
if(cnt==n-)
{
if(ans[cnt]==-) ans[cnt]=sum;
else ans[cnt]=min(ans[cnt],sum);
}
}
else //将未选中的边加入优先队列
que.push(edge[i].w);
}
if(cnt<n-) return;
while(!que.empty())
{
sum+=que.top();
que.pop();
++cnt;
if(ans[cnt]==-) ans[cnt]=sum;
else ans[cnt]=min(ans[cnt],sum);
}
}
int main()
{
int T;
scanf("%d",&T);
int kase=;
while(T--)
{
scanf("%d%d",&n,&m);
char c;
for(int i=;i<m;i++)
{
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
getchar();
c=getchar();
if(c=='B') edge[i].c=;
else if(c=='R') edge[i].c=;
else edge[i].c=;
}
memset(ans,-,sizeof(ans));
sort(edge,edge+m);
kruskal(); //第一种方案颜色不可为蓝色
kruskal(); //第二种方案颜色不可为红色
printf("Case #%d:\n",++kase);
for(int i=;i<=m;i++)
printf("%d\n",ans[i]);
}
}