征兵

【题目描述】：

一个国王，他拥有一个国家。最近他因为国库里钱太多了，闲着蛋疼要征集一只部队要保卫国家。他选定了N个女兵和M个男兵，但事实上每征集一个兵他就要花10000RMB，即使国库里钱再多也伤不起啊。他发现，某男兵和某女兵之间有某种关系（往正常方面想，一共R种关系），这种关系可以使KING少花一些钱就可以征集到兵，不过国王也知道，在征兵的时候，每一个兵只能使用一种关系来少花钱。这时国王向你求助，问他最少要花多少的钱。

【输入描述】：

第一行：T，一共T组数据。

接下来T组数据，

第一行包括N,M,R

接下来的R行 包括Xi,Yi,Vi 表示如果招了第Xi个女兵，再招第Yi个男兵能省Vi元（同样表示如果招了第Yi个男兵，再招第Xi个女兵能也省Vi元）

【输出描述】：

共T行，表示每组数据的最终花费是多少（因为国库里的钱只有2^31-1，所以保证最终花费在maxlongint范围内）

【样例输入】：

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

【样例输出】：

71071
54223

【时间限制、数据范围及描述】：

时间：1s 空间：128M

T<=5 ,m,n<=10000,r<=50000,Xi<=m,Yi<=n,Vi<=10000,结果<=2^31-1

最小生成树题。

注意：是 省多少钱 ，不是 花多少钱。。。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 10010
#define MAXM 50010
using namespace std;
int n,m,r,c,fa[MAXN<<1];
struct node{int u,v,w;
}a[MAXM<<1];
inline int read(){int date=0,w=1;char c=0;while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}return date*w;
}
bool cmp(const node &x,const node &y){return x.w<y.w;
}
void add(int u,int v,int w){a[c].u=u;a[c].v=v;a[c].w=w;c++;
}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void uniun(int x,int y){x=find(x);y=find(y);if(x!=y)fa[y]=x;}
int kruskal(){int ans=0,s=0;for(int i=1;i<c;i++)if(find(a[i].u)!=find(a[i].v)){uniun(a[i].u,a[i].v);ans+=a[i].w;s++;}return ans;
}
void init(){int u,v,w;c=1;for(int i=1;i<=n+m;i++)fa[i]=i;for(int i=1;i<=r;i++){u=read();v=read();w=read();u++;v++;v+=n;w=10000-w;add(u,v,w);add(v,u,w);}sort(a+1,a+c,cmp);
}
void work(){int ans=kruskal();for(int i=1;i<=n+m;i++)if(fa[i]==i)ans+=10000;printf("%d\n",ans);
}
int main(){int t;t=read();while(t--){n=read();m=read();r=read();init();work();}return 0;
}

征兵

【题目描述】：

一个国王，他拥有一个国家。最近他因为国库里钱太多了，闲着蛋疼要征集一只部队要保卫国家。他选定了N个女兵和M个男兵，但事实上每征集一个兵他就要花10000RMB，即使国库里钱再多也伤不起啊。他发现，某男兵和某女兵之间有某种关系（往正常方面想，一共R种关系），这种关系可以使KING少花一些钱就可以征集到兵，不过国王也知道，在征兵的时候，每一个兵只能使用一种关系来少花钱。这时国王向你求助，问他最少要花多少的钱。

【输入描述】：

第一行：T，一共T组数据。

接下来T组数据，

第一行包括N,M,R

接下来的R行 包括Xi,Yi,Vi 表示如果招了第Xi个女兵，再招第Yi个男兵能省Vi元（同样表示如果招了第Yi个男兵，再招第Xi个女兵能也省Vi元）

【输出描述】：

共T行，表示每组数据的最终花费是多少（因为国库里的钱只有2^31-1，所以保证最终花费在maxlongint范围内）

【样例输入】：

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

【样例输出】：

71071
54223

【时间限制、数据范围及描述】：

时间：1s 空间：128M

T<=5 ,m,n<=10000,r<=50000,Xi<=m,Yi<=n,Vi<=10000,结果<=2^31-1

最小生成树题。

注意：是 省多少钱 ，不是 花多少钱。。。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 10010
#define MAXM 50010
using namespace std;
int n,m,r,c,fa[MAXN<<1];
struct node{int u,v,w;
}a[MAXM<<1];
inline int read(){int date=0,w=1;char c=0;while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}return date*w;
}
bool cmp(const node &x,const node &y){return x.w<y.w;
}
void add(int u,int v,int w){a[c].u=u;a[c].v=v;a[c].w=w;c++;
}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void uniun(int x,int y){x=find(x);y=find(y);if(x!=y)fa[y]=x;}
int kruskal(){int ans=0,s=0;for(int i=1;i<c;i++)if(find(a[i].u)!=find(a[i].v)){uniun(a[i].u,a[i].v);ans+=a[i].w;s++;}return ans;
}
void init(){int u,v,w;c=1;for(int i=1;i<=n+m;i++)fa[i]=i;for(int i=1;i<=r;i++){u=read();v=read();w=read();u++;v++;v+=n;w=10000-w;add(u,v,w);add(v,u,w);}sort(a+1,a+c,cmp);
}
void work(){int ans=kruskal();for(int i=1;i<=n+m;i++)if(fa[i]==i)ans+=10000;printf("%d\n",ans);
}
int main(){int t;t=read();while(t--){n=read();m=read();r=read();init();work();}return 0;
}