【题目链接】 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;
}