題目大意：征兵，需要征募女兵N人，男兵M人，每征募一人需要花10000刀（貴死了~），但是軍隊頭子老奸巨猾，他知道自己所征募的人中有些互相有不可描述的關系（只限男女別想多了），若是征募關系親密的人就可以少花一些錢。機智的頭子決定靠這個來減少開支。于是，現在給出若干男女之間的1~9999之間的親密度關系，征募某個人所需費用為10000-（已經征募的人中和自己的親密度的最大值）?，F在要求你通過適當的征募順序使得軍隊頭子征募人花錢最少（好好添油加醋了一番了各位笑笑作罷QWQ）。 限制條件：1<=N,M<=10000; 0<=R<=50000; 0
#include<cstdio>#include<algorithm>#define MAX_E 50000#define MAX_V 20000using namespace std;struct edge{int fm,to,cost;};edge es[MAX_E];int par[MAX_V];void init(int n){ for(int i=0;i<n;i++) par[i]=i;}int find(int x){ if(par[x]==x) return x; return par[x]=find(par[x]);}bool same(int x,int y){ return find(x)==find(y);}void unite(int x,int y){ x=find(x),y=find(y); par[y]=x;}bool cmp(const edge &e1,const edge &e2){ return e1.cost<e2.cost;}int n,m,r;int Kruskal(){ sort(es,es+r,cmp); init(n+m); int ans=0; for(int i=0;i<r;i++){ edge e=es[i]; if(!same(e.fm,e.to)){ unite(e.fm,e.to); ans+=e.cost; } } return ans;}int main(){ while(scanf("%d %d %d",&n,&m,&r)!=EOF){ int x,y,d; for(int i=0;i<r;i++){ scanf("%d %d %d",&x,&y,&d); es[i]=(edge){x,n+y,-d};//女士優先+_+，男的在并查集中排在女的后面; } 很典型的Kruskal算法與并查集的模板，對該算法有所疑問的可以移步我之前寫的博客 http://blog.csdn.net/QQ91239497/article/details/54935979 感謝各位看官，共同進步哦！新聞熱點
疑難解答
