考虑分别求出RG和GB的最小生成树，然后剩下的边中肯定选择较小的边加入这两颗生成树
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 105 4 struct ji{ 5 int x,y,z; 6 char s[11]; 7 }e[N]; 8 vector<int>v; 9 int t,n,m,f[N],ans[N]; 10 bool cmp(ji x,ji y){ 11 return x.z<y.z; 12 } 13 int find(int k){ 14 if (k==f[k])return k; 15 return f[k]=find(f[k]); 16 } 17 void tree(char c){ 18 int tot=0,sum=0; 19 for(int i=1;i<=n;i++)f[i]=i; 20 v.clear(); 21 for(int i=1;i<=m;i++) 22 if (e[i].s[0]==c)v.push_back(e[i].z); 23 else 24 if (find(e[i].x)==find(e[i].y))v.push_back(e[i].z); 25 else{ 26 tot++; 27 sum+=e[i].z; 28 f[find(e[i].x)]=find(e[i].y); 29 } 30 if (tot<n-1)return; 31 ans[tot]=min(ans[tot],sum); 32 for(int i=0;i<v.size();i++){ 33 sum+=v[i]; 34 ans[++tot]=min(ans[tot],sum); 35 } 36 } 37 int main(){ 38 scanf("%d",&t); 39 for(int ii=1;ii<=t;ii++){ 40 scanf("%d%d",&n,&m); 41 for(int i=1;i<=m;i++)scanf("%d%d%d%s",&e[i].x,&e[i].y,&e[i].z,e[i].s); 42 sort(e+1,e+m+1,cmp); 43 memset(ans,0x3f,sizeof(ans)); 44 tree('B'); 45 tree('R'); 46 printf("Case #%d:\n",ii); 47 for(int i=1;i<=m;i++) 48 if (ans[i]==0x3f3f3f3f)printf("-1\n"); 49 else printf("%d\n",ans[i]); 50 } 51 }