点击这里查看原题
对于每个点，可以选择守横向或者守纵向。每行为一个点，每列为一个点，于是对于w[i][j]，在i与j+n之间连一条权值为w[i][j]的边，然后去求带一个环的最小生成树，这样刚好有n+m条边，而且每条边都连了一个横行和一个纵行，也就是每条边代表了一个守卫。
/* User:Small Language:C++ Problem No.:4883 */ #include<bits/stdc++.h> #define ll long long using namespace std; const int M=1e5+5; int n,m,tot,pre[M]; bool v[M]; ll ans; struct edge{ int u,v,w; bool operator<(const edge b)const{ return w<b.w; } }e[M]; int get(int x){ return x==pre[x]?x:pre[x]=get(pre[x]); } int main(){ freopen("data.in","r",stdin);// scanf("%d%d",&n,&m); for(int i=1;i<=n+m;i++) pre[i]=i; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ int z; scanf("%d",&z); e[++tot]=(edge){i,j+n,z}; } } sort(e+1,e+tot+1); for(int i=1;i<=tot;i++){ int x=get(e[i].u),y=get(e[i].v); if(v[x]&&v[y]) continue; if(x!=y){ v[y]|=v[x]; pre[x]=y; } else v[x]=1; ans+=e[i].w; } printf("%lld\n",ans); return 0; }