「NOIP模拟赛」征兵
一个国王，他拥有一个国家。最近他因为国库里钱太多了，闲着蛋疼要征集一只部队要保卫国家。他选定了N个女兵和M个男兵，但事实上每征集一个兵他就要花10000RMB，即使国库里钱再多也伤不起啊。他发现，某男兵和某女兵之间有某种关系（往正常方面想，一共R种关系），这种关系可以使KING少花一些钱就可以征集到兵，不过国王也知道，在征兵的时候，每一个兵只能使用一种关系来少花钱。这时国王向你求助，问他最少要花多少的钱。
读入（conscription.in）
第一行：T，一共T组数据。
接下来T组数据，
第一行包括N,M,R
接下来的R行 包括Xi,Yi,Vi 表示如果招了第Xi个女兵，再招第Yi个男兵能省Vi元（同样表示如果招了第Yi个男兵，再招第Xi个女兵能也省Vi元）
输出（conscription.out）
共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
数据范围
数据保证T<=5 ,m,n<=10000,r<=50000,Xi<=m,Yi<=n,Vi<=10000,结果<=2^31-1
直接最大生成树不解释
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #define inf 0x7fffffff #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,n,m,r; int fa[20005]; struct data{int x,y,v;}e[50005]; inline bool operator<(data a,data b) {return a.v>b.v;} int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);} int main() { //freopen("conscription.in","r",stdin); //freopen("conscription.out","w",stdout); T=read(); while(T--) { int ans=0; n=read();m=read();r=read(); for(int i=1;i<=n+m;i++)fa[i]=i; for(int i=1;i<=r;i++) { e[i].x=read();e[i].y=read();e[i].v=read(); e[i].x++;e[i].y++; e[i].y+=n; } sort(e+1,e+r+1); for(int i=1;i<=r;i++) { int p=find(e[i].x),q=find(e[i].y); if(p!=q)fa[p]=q,ans+=e[i].v; } printf("%d\n",(n+m)*10000-ans); } return 0; } |
Subscribe
计数器 9787587
OI 课件=>
OI 课件=>