題干：

Windy has a country, and he wants to build an army to protect his country. He has picked up?N?girls and?M?boys and wants to collect them to be his soldiers. To collect a soldier without any privilege, he must pay 10000 RMB. There are some relationships between girls and boys and Windy can use these relationships to reduce his cost. If girl?x?and boy?y?have a relationship?d?and one of them has been collected, Windy can collect the other one with 10000-d?RMB. Now given all the relationships between girls and boys, your assignment is to find the least amount of money Windy has to pay. Notice that only one relationship can be used when collecting one soldier.

Input

The first line of input is the number of test case.
The first line of each test case contains three integers,?N,?M?and?R.
Then?R?lines followed, each contains three integers?xi,?yi?and?di.
There is a blank line before each test case.

1 ≤?N,?M?≤ 10000
0 ≤?R?≤ 50,000
0 ≤?xi?<?N
0 ≤?yi?<?M
0 <?di?< 10000

Output

For each test case output the answer in a single line.

Sample Input

25 5 8 4 3 6831 1 3 4583 0 0 6592 0 1 3063 3 3 4975 1 3 2049 4 2 2104 2 2 7815 5 10 2 4 9820 3 2 6236 3 1 8864 2 4 8326 2 0 5156 2 0 1463 4 1 2439 0 4 4373 3 4 8889 2 4 3133

Sample Output

71071 54223

題目大意：

Windy有一個(gè)國(guó)家，他想建立一支軍隊(duì)來(lái)保護(hù)他的國(guó)家。他收留了N個(gè)女孩和M個(gè)男孩，想把她們收留成他的士兵。征兵無(wú)特權(quán)，必須交納一萬(wàn)元。女孩和男孩之間有一些關(guān)系，溫迪可以利用這些關(guān)系來(lái)降低他的成本。如果X女孩和Y男孩有D關(guān)系，并且其中一個(gè)已經(jīng)被收集，Windy可以用10000-D人民幣收集另一個(gè)。現(xiàn)在考慮到男孩和女孩之間的所有關(guān)系，你的任務(wù)是找到風(fēng)必須支付的最少的錢。注意，收集一個(gè)士兵時(shí)只能使用一個(gè)關(guān)系。

解題報(bào)告：

? 首先問(wèn)題轉(zhuǎn)化成：為了招到每個(gè)人 都先給每個(gè)人10000元，但是因?yàn)橐恍┻x擇的關(guān)系，使得可以再還回來(lái)一些錢。

? 建圖，這題把R個(gè)關(guān)系轉(zhuǎn)換成R條無(wú)向邊，每個(gè)士兵只能用一個(gè)關(guān)系說(shuō)明圖中選擇某些邊，但是邊構(gòu)成的圖不能有環(huán)（不難想到是棵樹，至于為什么是一棵樹而不能形成回路 比如a--b--c--d四人 a參軍影響b b參軍影響c?c參軍影響d?此時(shí)a已參軍 d無(wú)法影響a 構(gòu)不成回路）。然后要還回來(lái)的錢最多，所以要選擇邊權(quán)最大的邊來(lái)構(gòu)成這棵樹。于是轉(zhuǎn)化成最大生成樹問(wèn)題，不過(guò)這里要注意不一定是選擇的這棵樹包含所有的頂點(diǎn)，因?yàn)橹灰菢渚托袉h，不一定非連通所有的頂點(diǎn)啊，沒(méi)有連通的頂點(diǎn)我就付給他10000元就是了。所以最后用預(yù)付的每個(gè)人10000 減去? 最大生成樹的權(quán)值? 就是我們支付的最少的錢了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; int f[MAX]; int n,m,all,R; struct Edge {int u,v;ll w; } e[MAX]; bool cmp(Edge a,Edge b) {return a.w > b.w; } int getf(int v) {return v == f[v] ? v : f[v] = getf(f[v]); } void merge(int u,int v) {int t1 = getf(u);int t2 = getf(v);f[t2] = t1; } int main() {int t;cin>>t;while(t--) {cin>>n>>m;//n女孩 m男孩 all = n+m;for(int i = 1; i<=all; i++) f[i] = i;cin>>R;//R個(gè)關(guān)系 for(int x,y,i = 1; i<=R; i++) {ll d;scanf("%d%d%lld",&x,&y,&d);x++,y++;y+=n;e[i].u = x;e[i].v = y;e[i].w = d;}ll ans = 0;sort(e+1,e+R+1,cmp);for(int u,v,i = 1; i<=R; i++) {u = e[i].u,v = e[i].v;if(getf(u) != getf(v)) {merge(u,v);ans += e[i].w;}}printf("%lld\n",all*10000LL - ans); }return 0 ; } /* 25 5 8 4 3 6831 1 3 4583 0 0 6592 0 1 3063 3 3 4975 1 3 2049 4 2 2104 2 2 781*/

注意轉(zhuǎn)化關(guān)系，每個(gè)人的關(guān)系只能使用一次，類似的問(wèn)題，可以轉(zhuǎn)化成每個(gè)頂點(diǎn)的入度？出度？這題中是轉(zhuǎn)化成不能有環(huán)的問(wèn)題，其實(shí)題目中表達(dá)的不是很清晰。

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的【POJ - 3723】Conscription （最大生成树，最小生成树MST变形）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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