Conscription

Total Submission(s) : 13   Accepted Submission(s) : 6

Problem Description

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算法，让男生直接+maxn就好；

``` 1 #include<stdio.h>
2 #include<string.h>
3 #include<algorithm>
4 using namespace std;
5 const int MAXN=10010;
6 struct Node{
7     int s,e,c;
8 };
9 int cmp(Node a,Node b){
10     return a.c>b.c;
11 }
12 Node dt[MAXN*5];
13 int pre[MAXN*2];
14 int ans;
15 int find(int x){
16     return pre[x]= x==pre[x]?x:find(pre[x]);
17 }
18 void initial(){
19     memset(pre,-1,sizeof(pre));
20     ans=0;
21 }
22 void merge(Node a){
23         int f1,f2;
24     if(pre[a.s]==-1)pre[a.s]=a.s;
25     if(pre[a.e]==-1)pre[a.e]=a.e;
26     f1=find(a.s);f2=find(a.e);
27     if(f1!=f2){
28         pre[f1]=f2;
29         ans+=a.c;
30     }
31 }
32 int main(){int N,M,R,T;
33 scanf("%d",&T);
34     while(T--){
35         scanf("%d%d%d",&N,&M,&R);
36         initial();
37         for(int i=0;i<R;i++){
38             scanf("%d%d%d",&dt[i].s,&dt[i].e,&dt[i].c);
39             dt[i].e+=MAXN;
40         }
41         sort(dt,dt+R,cmp);
42         for(int i=0;i<R;i++){
43             merge(dt[i]);
44         }
45         printf("%d\n",10000*(M+N)-ans);
46     }
47     return 0;
48 }```

Conscription POJ - 3723

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 relationshi

POJ 3723 Conscription

http://poj.org/problem?id=3723 这道题 把男生画一边 女生画一边 ---->是一个二部图的结构 就很容易看出 要pay最少 实际上就是找到一个连接所有点权值和最大的图 但是又要求 一个人只能使用一种关系减钱 所以不能有回路 ---->是一棵树 所以就是求最大生成树 有了前面并查集题目的经验 我们可以让i < N为女生 i >=N 作为男生 来维持这个并查集 那么就自然的使用Kruskal即可 1 #include <iostream> 2

poj - 3723 Conscription(最大权森林）

http://poj.org/problem?id=3723 windy需要挑选N各女孩,和M各男孩作为士兵,但是雇佣每个人都需要支付10000元的费用,如果男孩x和女孩y存在亲密度为d的关系,只要他们其中有一个已经被选中,那么在选另一个人需要的费用为100000-d,给定R个关系,输出一个最低费用,每个关系只能使用一次. 把人看作顶点,关系看作边,就可以转化为无向图中的最大权森林问题,最大权森林问题可以通过把所有边权取反之后用最小生成树的算法求解. 1 #include <cstdio> 2

poj3723_Conscription

Conscription Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 12393   Accepted: 4350 Description 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 b

题单二：图论500

http://wenku.baidu.com/link?url=gETLFsWcgddEDRZ334EJOS7qCTab94qw5cor8Es0LINVaGMSgc9nIV-utRIDh--2UwRLvsvJ5tXFjbdpzbjygEdpGehim1i5BfzYgYWxJmu ==========  以下是最小生成树+并查集=========================[HDU]1213         How Many Tables        基础并查集★1272         小

(最大生成树) poj 3727

Conscription Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 8330   Accepted: 2894 Description 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