点击打开链接
虽是二分图 但在此题中男女其实可以看做同一类型 都是点与点之间的关系
两人之间的关系价值就是边长 用这些边凑最大生成树(边长就是优惠值 优惠越多越好) 虽然有可能不是一颗完整的生成树
个人感觉题意中比较难理解的就是 "Notice that only one relationship can be used when collecting one soldier."
一开始觉得这个条件与生成树相矛盾:一个点的所有相关联的边只能选其一 根本无法形成连通图
其实就是当两点之间有多个关系时只能用其中一个 样例中就有
至于为什么是一棵树而不能形成回路 比如a--b--c--d四人 a参军影响b b参军影响c c参军影响d 此时a已参军 d无法影响a 构不成回路
#include <stdio.h> #include <algorithm> using namespace std; struct node { int u; int v; long long w; }; struct node edge[50001]; int f[20001]; int n,m; int cmp(node n1,node n2) { return n1.w>n2.w; } int unite(int u,int v); int getf(int p); int main() { long long w,sum; int t,i,j,u,v,n1,n2,cnt; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n1,&n2,&m); n=n1+n2; for(i=1;i<=m;i++) { scanf("%d%d%lld",&u,&v,&w); u++,v++; u+=n2; edge[i].u=u,edge[i].v=v,edge[i].w=w; } sort(edge+1,edge+m+1,cmp); for(i=1;i<=n;i++) { f[i]=i; } cnt=0,sum=0; for(i=1;i<=m;i++) { if(unite(edge[i].u,edge[i].v)) { sum+=edge[i].w; cnt++; } if(cnt==n-1) break; } sum=n*10000-sum; printf("%lld\n",sum); } return 0; } int unite(int u,int v) { int fu,fv; fu=getf(u); fv=getf(v); if(fu!=fv) { f[fv]=fu; return 1; } else return 0; } int getf(int p) { if(f[p]==p) return p; else { f[p]=getf(f[p]); return f[p]; } }
