首页 > 代码库 > [bzoj4883][Lydsy2017年5月月赛]棋盘上的守卫
[bzoj4883][Lydsy2017年5月月赛]棋盘上的守卫
来自FallDream的博客，未经允许，请勿转载， 谢谢。
在一个n*m的棋盘上要放置若干个守卫。对于n行来说，每行必须恰好放置一个横向守卫；同理对于m列来说，每列
必须恰好放置一个纵向守卫。每个位置放置守卫的代价是不一样的，且每个位置最多只能放置一个守卫，一个守卫
不能同时兼顾行列的防御。请计算控制整个棋盘的最小代价。
n*m<=10^5
费用流比较好想，把行和列拿出来，第i行向第j列连费用是a[i][j]的边，然后限制每行每列流量1即可。
但是费用流不是很科学（好像有人大力艹过了？），考虑优化。
费用流每次的增广路其实就是选择了费用最小的一行一列，假如把a[i][j]看作i->j的边，那么得到的显然会是一个环套树森林。
那么就跑最小生成树，然后记录每个点所在连通块是树还是图即可。
假如要合并i,j
如果ij都是图了，那么就没办法咯。
不然，i,j在同一个集合时加入这条边即可 树->图 ； 不在同一个集合的话，就把他们并起来，然后判断得到的是一个什么图形。
如果原来是树+树，得到树，树+图得到图。
复杂度nmlog(nm)
#include<iostream>#include<cstdio>#include<algorithm>#define rint register int #define getchar() (*S++)#define MN 100000#define ll long longchar B[1<<26],*S=B;using namespace std;inline int read(){ int x = 0 , f = 1; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘){ if(ch == ‘-‘) f = -1; ch = getchar();} while(ch >= ‘0‘ && ch <= ‘9‘){x = x * 10 + ch - ‘0‘;ch = getchar();} return x * f;}int n,m,cnt=0,fa[MN*2+5];ll ans=0;struct data{int x,c,r;}a[MN+5]; bool b[MN*2+5];bool cmp(data a,data b){return a.x<b.x;}inline int getfa(int x){return !fa[x]?x:fa[x]=getfa(fa[x]);}int main(){ fread(B,1,1<<26,stdin); n=read();m=read(); for(rint i=1;i<=n;++i) for(rint j=1;j<=m;++j) a[++cnt]=(data){read(),i,j+n}; sort(a+1,a+cnt+1,cmp); for(rint i=1;i<=cnt;++i) { int x=getfa(a[i].c),y=getfa(a[i].r); if(!(b[x]&b[y])) { if(x!=y) fa[x]=y,b[y]|=b[x]; else b[x]=1; ans+=a[i].x; } } printf("%lld\n",ans); return 0;}
[bzoj4883][Lydsy2017年5月月赛]棋盘上的守卫
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。