Conscription [POJ3723] [最小生成树]

Description：

Windy有一个国家，他想建立一个军队来保护他的国家。他召集了N个女孩和M男孩，想把他们雇佣成为他的士兵。要无偿雇佣士兵，必须支付10000元。女孩和男孩之间有一些关系，而Windy可以利用这些关系来降低他的成本。如果女孩x和男孩y有关系，并且其中一个已经被收集，Windy可以以10000-d的价格雇佣另一个。现在给予女孩和男孩之间的所有关系，你的任务是找到Windy必须支付的最少的钱。请注意，雇佣一名士兵时只能使用一种关系。

Input：
第一行输入是测试用例的数量。
每个测试用例的第一行包含三个整数N，M和R.
然后是R行，每行包含三个整数xi，yi和di。
每个测试用例前都有一个空白行。

1≤N，M≤10000
0≤R≤50000，0≤xi<N，0≤yi<M，0 <di <10000
Output：
对于每个测试用例，都会在一行中输出答案。

Sample Input：

    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 Input：
71071
54223

Analysis：

首先，我们可以发现这是一个二分图！

然后，看了很久，我们发现好像这个二分图的性质并没有什么用。

如果有一些点被一些线连在了一起（连通块），那我们发现，只要有一个点花10000块钱买了下来，剩下的点都可以得到优惠，优惠的价格便是边权。

那相当于，一条边能对连接他的两个端点产生优惠，换而言之，其中一个点的价格便变成了（10000-边权）。

于是我们发现，便是在一个连通块里求最小生成树（边权改为10000-输入值的边权），在加上连通块的个数即可。

Code：

 1 #include<set>
 2 #include<map>
 3 #include<queue>
 4 #include<stack>
 5 #include<cmath>
 6 #include<cstdio>
 7 #include<cstring>
 8 #include<iostream>
 9 #include<algorithm>
10 #define RG register int
11 #define rep(i,a,b)    for(RG i=a;i<=b;++i)
12 #define per(i,a,b)    for(RG i=a;i>=b;--i)
13 #define ll long long
14 #define inf (1<<29)
15 #define maxn 10005
16 #define maxe 50005
17 using namespace std;
18 int T,n,m,ec,blk,ans;
19 int fa[maxn<<1],vis[maxn<<1];
20 struct E{
21     int u,v,val;
22     inline int operator < (const E &a)const{
23         return val<a.val;
24     }
25 }e[maxe];
26 inline int read()
27 {
28     int x=0,f=1;char c=getchar();
29     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
30     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
31     return x*f;
32 }
33 
34 int find(int x)
35 {
36     if(fa[x]==x)    return x;
37     return fa[x]=find(fa[x]);
38 }
39 
40 int mst()
41 {
42     int sum=0;RG fu,fv;
43     rep(i,1,n+m)    fa[i]=i;
44     sort(e+1,e+1+ec);    
45     rep(i,1,ec)
46     {
47         fu=find(e[i].u),fv=find(e[i].v);
48         if(fu!=fv)    sum+=e[i].val,fa[fu]=fv;
49     }
50     return sum;
51 }
52 
53 int main()
54 {
55     T=read();
56     while(T--)
57     {
58         n=read(),m=read(),ec=read();
59         rep(i,1,ec)    e[i].u=read()+1,e[i].v=read()+n+1,e[i].val=10000-read();
60         ans=mst();
61         int bl;blk=0;
62         rep(i,1,n+m)
63         {
64             bl=find(i);
65             if(!vis[bl])    vis[bl]=1,blk++;
66         }
67         cout<<blk*10000+ans<<endl;
68         memset(vis,0,sizeof(vis));
69     }
70     return 0;
71 }

View Code