有上下界的网络流（最大流）模板

有上下界的网络流（最大流）模板

P4311 士兵占领

没有障碍的格子，上界为1，下界是0

#include 
#define inf 0x7fffffff
#define ll long long
//#define int long long 
//#define double long double
#define re register int
#define void inline void
#define eps 1e-8
//#define mod 1e9+7
#define ls(p) p<<1
#define rs(p) p<<1|1
#define pi acos(-1.0)
#define pb push_back
#define P pair < int , int >
#define mk make_pair
using namespace std;
const int mod=19940417;
const int M=1e9;
const int N=2e6+5;//?????????? 4e8
int tot=1,head[N];
struct node
{
	int ver,edge,next;
}e[N];
int a[155][155];
int n,m,s,t,k;
int sum[N],gap[N],d[N];
int cnt,ans;
void add(int x,int y,int z)
{
	e[++tot].ver=y;
	e[tot].edge=z;
	e[tot].next=head[x];
	head[x]=tot;
}
void addedge(int x,int y,int z)
{
	add(x,y,z);add(y,x,0);
}
void bfs()
{
	queue < int > q;
	for(re i=s;i<=t;i++)  d[i]=gap[i]=0;
	d[t]=gap[1]=1;q.push(t);
	while(q.size())
	{
		int x=q.front();q.pop();
		for(re i=head[x];i;i=e[i].next)
		{
			int y=e[i].ver;
			if(d[y])  continue;
			d[y]=d[x]+1;
			gap[d[y]]++;
			q.push(y);
		}
	}
}
int dfs(int x,int flow)
{
	if(x==t)  return flow;
	int rest=0;
	for(re i=head[x];i;i=e[i].next)
	{
		int y=e[i].ver;
		int z=e[i].edge;
		if(!z)  continue;
		if(d[x]!=d[y]+1)  continue;
		int k=dfs(y,min(z,flow-rest));
		if(!k)  continue;
		e[i].edge-=k;
		e[i^1].edge+=k;
		rest+=k;
		if(rest==flow)  return flow;
	}
	if(--gap[d[x]]==0)  d[s]=2*t+2;
	++gap[++d[x]];
	return rest;
}
int isap()
{
	int maxflow=0;
	bfs();
	while(d[s]<=2*t+1)  maxflow+=dfs(s,1e9);
	return maxflow; 
}
int b[N],c[N];
void solve()
{
	cin>>m>>n>>k;
	s=0,t=m+n+1;
	for(re i=1;i<=m;i++)  scanf("%d",&b[i]),ans+=b[i];
	for(re i=1;i<=n;i++)  scanf("%d",&c[i]),ans+=c[i];
	for(re i=1;i<=k;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		a[x][y]=1;
	}
	for(re i=1;i<=m;i++)  addedge(s,i,b[i]);
	for(re i=1;i<=n;i++)  addedge(i+m,t,c[i]);
	for(re i=1;i<=m;i++)  for(re j=1;j<=n;j++)
	{
		if(!a[i][j])  addedge(i,j+m,1);
		sum[i]=sum[i]+(!a[i][j]);
		sum[j+m]=sum[j+m]+(!a[i][j]);
	}
	for(re i=1;i<=m;i++)  if(b[i]>sum[i])
	{
		puts("JIONG!");
		return;
	}
	for(re i=1;i<=n;i++)  if(c[i]>sum[i+m])
	{
		puts("JIONG!");
		return;
	}
	printf("%dn",ans-isap());
}
signed main()
{
//	freopen("Ain.txt", "r", stdin);
//	freopen("Aout.txt", "w", stdout);
    int T=1;
//    cin>>T;
    for(int index=1;index<=T;index++)
    {
//        printf("Case #%lld: ",index);
        solve();
//        puts("");
    }
    return 0;
}