Conscription(POJ NO.3723)解题报告（最大生成树Kruskal算法）

2019-11-08 20:26:30

字体：大中小

来源：转载

供稿：网友

题目大意：征兵，需要征募女兵N人，男兵M人，每征募一人需要花10000刀（贵死了~），但是军队头子老奸巨猾，他知道自己所征募的人中有些互相有不可描述的关系（只限男女别想多了），若是征募关系亲密的人就可以少花一些钱。机智的头子决定靠这个来减少开支。于是，现在给出若干男女之间的1~9999之间的亲密度关系，征募某个人所需费用为10000-（已经征募的人中和自己的亲密度的最大值）。现在要求你通过适当的征募顺序使得军队头子征募人花钱最少（好好添油加醋了一番了各位笑笑作罢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};//女士优先+_+，男的在并查集中排在女的后面; } PRintf("%d/n",10000*(n+m)+Kruskal()); }}

很典型的Kruskal算法与并查集的模板，对该算法有所疑问的可以移步我之前写的博客 http://blog.csdn.net/QQ91239497/article/details/54935979 感谢各位看官，共同进步哦！

上一篇：遇到的小问题，不断更新

下一篇：##模拟实现strlen函数