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月月赛]棋盘上的守卫（最小生成环套树森林）

最新文章

热门文章