Conscription

Conscription

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 131072/65536K (Java/Other)
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

题解:

征兵:有n个女生,m个男生,其中每个人需要花费10000元。不过男生和女生之间有相互作用,可以降低费用。比如编号为1的女生和编号为1的男生之间有关系d,那么女生已经征兵结束后,男生只需10000-d即可入伍

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 }
时间: 08-11

Conscription的相关文章

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 题意需要征募男兵M人,女兵N人,每征募一个人需要10000元,但是已经征募 的人中有和待征募的人关系密切的可以少花点钱,求通过适当的顺序使得征募所有人所需的费用最小. 思路:这是二分图的背景,是陷阱,没用,征募a动用了a和b关系,那么(a,b)连成一条边,虽然这条边是有向的,但是不管是谁先征募最后的结果都相同所以是无向图的最大生成森林,使得关系利用到最大,然后把边权取反后就可以用基本的最小生成森林来解决了. //800K 3

POJ 3723 Conscription

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

poj 3723 Conscription(最大生成树)

题意:招募n个女生与m个男生,每人花费需10000,若两人间存在亲密度,则可少花费两人的亲密度,求最小花费: 思路:相当于一幅无向图,给定边权,求权值和最大的森林,结果为10000*(n+m)-权值和: #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; struct edge{ i

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         小

9.26 noip模拟试题

魔术球问题弱化版(ball.c/.cpp/.pas) 题目描述 假设有 n 根柱子,现要按下述规则在这 n 根柱子中依次放入编号为 1,2,3,…的球. (1)每次只能在某根柱子的最上面放球. (2)在同一根柱子中,任何 2 个相邻球的编号之和为完全平方数. 试设计一个算法,计算出在 n 根柱子上最多能放多少个球.例如,在 4 根柱子上最多可放 11 个球. 对于给定的 n,计算在 n 根柱子上最多能放多少个球. 输入描述 第 1 行有 1 个正整数 n,表示柱子数. 输出描述 一行表示可以放的

(最大生成树) 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