首页 > 代码库 > BZOJ 4883 [Lydsy2017年5月月赛]棋盘上的守卫（最小生成环套树森林）
BZOJ 4883 [Lydsy2017年5月月赛]棋盘上的守卫（最小生成环套树森林）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=4883
【题目大意】
在一个n*m的棋盘上要放置若干个守卫。
对于n行来说，每行必须恰好放置一个横向守卫；同理对于m列来说，
每列必须恰好放置一个纵向守卫。每个位置放置守卫的代价是不一样的，
且每个位置最多只能放置一个守卫，一个守卫不能同时兼顾行列的防御。
请计算控制整个棋盘的最小代价。
【题解】
我们将每行和每列看成一个点，用每个格子上的点的权值作为边，
这就构成了一个n+m个点的图。
我们发现对于n个点的集合，为了满足题目中的要求，就至少要包含n条边。
所以题目就转化成求图中的最小生成环套树森林。
【代码】
#include <cstdio>#include <algorithm>using namespace std;typedef long long LL;const int N=200010;LL ans;int x,n,m,f[N],v[N];struct E{int u,v,c;E(){}E(int u,int v,int c):u(u),v(v),c(c){};}e[N];bool cmp(E x,E y){return x.c<y.c;}int sf(int x){return x==f[x]?x:f[x]=sf(f[x]);}int main(){ while(~scanf("%d%d",&n,&m)){ int cnt=ans=0; for(int i=1;i<=n+m;i++)f[i]=i,v[i]=0; for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){ scanf("%d",&x); e[++cnt]=E(i,j+n,x); }sort(e+1,e+cnt+1,cmp); for(int i=1;i<=cnt;i++){ int fx=sf(f[e[i].u]),fy=sf(f[e[i].v]); if(v[fx]&&v[fy])continue; if(fx!=fy)v[fy]|=v[fx],f[fx]=fy;else v[fx]=1; ans+=e[i].c; }printf("%lld\n",ans); }return 0;}BZOJ 4883 [Lydsy2017年5月月赛]棋盘上的守卫（最小生成环套树森林）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。