POJ 3723 Conscription

http://poj.org/problem?id=3723

这道题把男生画一边女生画一边 ---->是一个二部图的结构

就很容易看出

要pay最少实际上就是找到一个连接所有点权值和最大的图

但是又要求一个人只能使用一种关系减钱所以不能有回路 ---->是一棵树

所以就是求最大生成树

有了前面并查集题目的经验我们可以让i < N为女生 i >=N 作为男生来维持这个并查集

那么就自然的使用Kruskal即可

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <algorithm>
 5 #define MAXV 20007
 6 #define MAXE 100007
 7 #define INF 0x3f3f3f3f
 8 using namespace std;
 9 
10 struct Edge
11 {
12     int from, to, cost;
13     Edge () {}
14     Edge (int from, int to, int cost) : from(from), to(to), cost(cost) {}
15 }edge[MAXE];
16 int num = 0;
17 int par[MAXV];
18 int find(int x)
19 {
20     if (par[x] == x) return x;
21     else return par[x] = find(par[x]);
22 }
23 void unite(int x, int y)
24 {
25     int px = find(x), py = find(y);
26     if (px == py) return;
27     par[py] = px;
28 }
29 bool same(int x, int y)
30 {
31     int px = find(x), py = find(y);
32     return px == py;
33 }
34 
35 bool cmp(Edge e1, Edge e2)
36 {
37     return e1.cost > e2.cost;
38 }
39 //主要就是画图 发现其实就是不能有回路 那就是最小生成树 偶不 最大生成树
40 //书上提醒 在这个问题中 完全没有用到男女之间的二分图结构 但是在许多问题中 有特殊地结构 往往要考虑如何利用这个结构
41 //也有像本题一样设置无用陷阱条件的题目!!
42 int Kruskal()
43 {
44     int res = 0;
45     sort(edge, edge+num, cmp);
46     for (int i = 0; i < num; i++)
47     {
48         Edge e = edge[i];
49         if (!same(e.from, e.to))
50         {
51             res += e.cost;
52             unite(e.from, e.to);
53         }
54     }
55     return res;
56 }
57 
58 int main()
59 {
60     int R, N, M, T;
61     freopen("in.txt", "r", stdin);
62     scanf("%d", &T);
63     while (T--)
64     {
65         scanf("%d%d%d", &N, &M, &R);//N girl , M boy
66         for (int i = 0; i< N; i++) par[i] = i;
67         for (int i = N; i < N+M; i++) par[i] = i;//i < N是girl i >= N 是Boy
68         num = 0;
69         for (int i = 0; i < R; i++)
70         {
71             int from, to, cost;
72             scanf("%d%d%d", &from, &to, &cost);
73             to += N;
74             edge[num++] = Edge(from, to, cost);
75             edge[num++] = Edge(to, from, cost);
76         }
77         int ans = 10000*(N+M);
78         ans -= Kruskal();
79         cout << ans << endl;
80     }
81     return 0;
82 
83 }