Conscription POJ - 3723 (最小生成树kruskal模板题)

清疚 2022-04-23 21:56 136阅读 0赞

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

2
    
    5 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
    
    5 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

解题思路:

我们可以不把这个图看成二分图,直接当成图处理就可以了

把每条边的权值取反,利用最小生成树kruskal算法求得最大权值,利用单个得总费用之和减去最大权值即可

注意顶点数是N+M,所以最大顶点数是20000个

#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <string.h>
    #include <stdio.h>
    using namespace std;
    const int MAXN = 30010;
    const int MAXE = 50010;
    int TC;
    int N, M, R;
    struct fsEdge {
    	int u, v, cost;
    }fsEdges[MAXE];
    int fsFather[MAXN];
    
    void initFather() {
    	for(int i = 0; i < N+M; ++i) {
    		fsFather[i] = i;  //初始化并查集
    	}
    }
    
    int fsFind(int x) {
    	if (fsFather[x] != x) {
    		fsFather[x] = fsFind(fsFather[x]);  //向下查找
    	}
    	return fsFather[x];
    }
    
    bool fsIsSame(int a, int b) {
    	int fa = fsFind(a);
    	int fb = fsFind(b);
    	if (fa == fb) return true;
    	else return false;
    }
    
    void unitFsSet(int a, int b) {
    	int fa = fsFind(a);
    	int fb = fsFind(b);
    	if (fa != fb) {
    		fsFather[fa] = fb;
    	}
    }
    
    bool fsCmp(fsEdge a, fsEdge b) {
    	return a.cost < b.cost;
    }
    
    int fsKruskal() {
    	sort(fsEdges, fsEdges + R, fsCmp);  //把所有边排个序
    	initFather();  //初始化并查集
    	int fsRes = 0;
    	for (int i = 0; i < R; ++i) {
    		fsEdge e = fsEdges[i];
    		if (!fsIsSame(e.u, e.v)) {
    			unitFsSet(e.u, e.v);   //合并
    			fsRes += e.cost;   //加上消费
    		}
    	}
    	return fsRes;
    }
    
    
    int main() {
    	scanf("%d", &TC);
    	while (TC--) {  
    		scanf("%d %d %d", &N, &M, &R);  //读入数据
    		int nx, ny, cc;
    		for (int i = 0; i < R; ++i) {
    			scanf("%d %d %d", &nx, &ny, &cc);
    			fsEdges[i].u = nx;
    			fsEdges[i].v = N + ny;
    			fsEdges[i].cost = -cc;  //取负值,这样最小生成树生成出来的结果的绝对值最大
    		}
    		int mintime = fsKruskal();
    		printf("%d\n", 10000 * (N + M) + mintime);   //求解
    	}
    	system("PAUSE");
    	return 0;
    }