首页 > 代码库 > [BZOJ 1458]士兵占领（网络流）
[BZOJ 1458]士兵占领（网络流）
Description
有一个M * N的棋盘，有的格子是障碍。现在你要选择一些格子来放置一些士兵，一个格子里最多可以放置一个士兵，障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘当满足第i行至少放置了Li个士兵, 第j列至少放置了Cj个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。
Solution
可以用上下界最小流来做，不过我觉得黄学长的这个思路也很直接
将每行每列都看成一个点，由s向行连边，容量为可以放置的士兵数-至少放置的士兵数
由列向t连边，容量为可以放置的士兵数-至少放置的士兵数
然后对于每个无障碍的点，由行向列连流量为1的边
这样跑最大流就可以得到最多可以删去多少个士兵啦
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<queue>#define INF 0x3f3f3f3f#define MAXN 105using namespace std;int s,t,m,n,k,l[MAXN],c[MAXN],la[MAXN],ca[MAXN],level[MAXN*3],head[MAXN*3],cnt=0;bool f[MAXN][MAXN];struct Node{ int next,to,cap;}Edges[MAXN*MAXN*4];int read(){ int x=0,f=1;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}void addedge(int u,int v,int w){ Edges[cnt].next=head[u]; head[u]=cnt; Edges[cnt].to=v,Edges[cnt++].cap=w;}void insert(int u,int v,int w){ addedge(u,v,w); addedge(v,u,0);}queue<int>q;bool bfs(){ memset(level,-1,sizeof(level)); q.push(s),level[s]=0; while(!q.empty()) { int u=q.front();q.pop(); for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(level[v]==-1&&Edges[i].cap) level[v]=level[u]+1,q.push(v); } } if(level[t]==-1)return false; return true;}int dfs(int u,int f){ if(u==t)return f; int flow=0,d; for(int i=head[u];~i&&flow<f;i=Edges[i].next) { int v=Edges[i].to; if(level[v]==level[u]+1&&Edges[i].cap) { d=dfs(v,min(f-flow,Edges[i].cap)); flow+=d; Edges[i].cap-=d; Edges[i^1].cap+=d; } } if(!flow)level[u]=-1; return flow;}int dinic(){ int res=0,d; while(bfs()) { while(d=dfs(s,INF)) res+=d; } return res;}int main(){ memset(head,-1,sizeof(head)); m=read(),n=read(),k=read(); s=0,t=m+n+1; for(int i=1;i<=m;i++)l[i]=read(),la[i]=n; for(int i=1;i<=n;i++)c[i]=read(),ca[i]=m; for(int i=1;i<=k;i++) { int x=read(),y=read(); la[x]--,ca[y]--; if(la[x]<l[x]||ca[y]<c[y]){printf("JIONG!\n");return 0;} f[x][y]=1; } for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) if(!f[i][j])insert(i,m+j,1); for(int i=1;i<=m;i++)insert(s,i,la[i]-l[i]); for(int i=1;i<=n;i++)insert(m+i,t,ca[i]-c[i]); printf("%d\n",m*n-k-dinic()); return 0;}
[BZOJ 1458]士兵占领（网络流）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。