題干：

度度熊有一張?nn?個(gè)點(diǎn)?mm?條邊的無(wú)向圖，所有點(diǎn)按照?1,2,?,n1,2,?,n?標(biāo)號(hào)，每條邊有一個(gè)正整數(shù)權(quán)值以及一種色光三原色紅、綠、藍(lán)之一的顏色。?

現(xiàn)在度度熊想選出恰好?kk?條邊，滿足只用這?k?條邊之中的紅色邊和綠色邊就能使?n?個(gè)點(diǎn)之間兩兩連通，或者只用這?kk?條邊之中的藍(lán)色邊和綠色邊就能使?nn?個(gè)點(diǎn)之間兩兩連通，這里兩個(gè)點(diǎn)連通是指從一個(gè)點(diǎn)出發(fā)沿著邊可以走到另一個(gè)點(diǎn)。?

對(duì)于每個(gè)?k=1,2,?,mk=1,2,?,m，你都需要幫度度熊計(jì)算選出恰好?kk?條滿足條件的邊的權(quán)值之和的最小值。?

Input

第一行包含一個(gè)正整數(shù)?TT，表示有?TT?組測(cè)試數(shù)據(jù)。?

接下來(lái)依次描述?TT?組測(cè)試數(shù)據(jù)。對(duì)于每組測(cè)試數(shù)據(jù)：?

第一行包含兩個(gè)整數(shù)?nn?和?mm，表示圖的點(diǎn)數(shù)和邊數(shù)。?

接下來(lái)?mm?行，每行包含三個(gè)整數(shù)?a,b,wa,b,w?和一個(gè)字符?cc，表示有一條連接點(diǎn)?aa?與點(diǎn)?bb?的權(quán)值為?ww、顏色為?cc?的無(wú)向邊。?

保證?1≤T≤1001≤T≤100，1≤n,m≤1001≤n,m≤100，1≤a,b≤n1≤a,b≤n，1≤w≤10001≤w≤1000，c∈{R,G,B}c∈{R,G,B}，這里?R,G,BR,G,B?分別表示紅色、綠色和藍(lán)色。?

Output

對(duì)于每組測(cè)試數(shù)據(jù)，先輸出一行信息 "Case #x:"（不含引號(hào)），其中 x 表示這是第?xx?組測(cè)試數(shù)據(jù)，接下來(lái)?mm?行，每行包含一個(gè)整數(shù)，第?ii?行的整數(shù)表示選出恰好?ii?條滿足條件的邊的權(quán)值之和的最小值，如果不存在合法方案，輸出??1?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

解題報(bào)告：

剛開(kāi)始讀錯(cuò)題了很尷尬、、題面說(shuō)的是 用k條紅色邊綠色邊 或者 用k條藍(lán)色邊綠色邊，我理解成了并且，也就是這k條邊必須僅用紅綠可以構(gòu)成生成樹(shù)，并且僅用藍(lán)綠也可以構(gòu)成生成樹(shù)了、、、如果是那樣的話就比較難考慮了。。不過(guò)這個(gè)題還好，直接用紅綠求一個(gè)，用藍(lán)綠求一個(gè)，這樣分成兩個(gè)獨(dú)立的問(wèn)題。對(duì)于每個(gè)問(wèn)題，先構(gòu)成MST，然后直接貪心加邊就行了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; const int INF = 0x3f3f3f3f; int n,m,flag[MAX],f[MAX],ans[MAX]; struct Edge {int u,v,w;int col;//0綠 1紅 2藍(lán)Edge(int u=0,int v=0,int w=0,int col=0):u(u),v(v),w(w),col(col) {}friend bool operator < (Edge a,Edge b) {return a.w < b.w;} } e[MAX]; int getf(int v) {return f[v] == v ? v : f[v] = getf(f[v]); } void init() {for(int i = 1; i<=n; i++) f[i] = i;for(int i = 1; i<=m; i++) flag[i] = 0; } void Klu(int col) {init();int res = 0,cnt = 0;for(int u,v,i = 1; i<=m; i++) {u = getf(e[i].u); v = getf(e[i].v);if(u == v || e[i].col == col) continue;f[v] = u;cnt++;res += e[i].w;flag[i] = 1;}if(cnt < n-1) return;int top = n-1;ans[top] = min(ans[top],res);for(int i = 1; i<=m; i++) {if(flag[i] == 1) continue;res += e[i].w;top++;ans[top] = min(ans[top],res);} } int main() {int t,iCase=0;char s[5];cin>>t;while(t--) {scanf("%d%d",&n,&m);for(int i = 1; i<=m; i++) ans[i] = INF;for(int a,b,c,i = 1; i<=m; i++) {scanf("%d%d%d%s",&a,&b,&c,s);e[i] = Edge(a,b,c,0);if(s[0] == 'R') e[i].col = 1;if(s[0] == 'B') e[i].col = 2;}sort(e+1,e+m+1);Klu(1);Klu(2); printf("Case #%d:\n",++iCase);for(int i = 1; i<=m; i++) {if(ans[i] == INF) puts("-1");else printf("%d\n",ans[i]);}}return 0 ; }/* 1 3 6 1 2 100 G 2 3 100 G 1 2 1 B 2 3 10 B 1 2 2 R 2 3 20 R Case #1: -1 11 13 33 133 233 */

讀錯(cuò)題太可怕了，直接由一個(gè)水題變成一個(gè)不可做題、、?

總結(jié)

以上是生活随笔為你收集整理的【HDU - 6349】三原色图（最小生成树，思维，tricks）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。