bzoj1458: 士兵占领 网络流

链接

https://www.lydsy.com/JudgeOnline/problem.php?id=1458

也可以去luogu

思路

想成倒着删去点，使得依旧满足覆盖！！

左边横，右边列，之间用点链接起来，流量1

S到i为之间总公共 最多去掉m-h[i]-L[i]个，i到T同理。

代码

#include <iostream>

#include <queue>

#include <cstdio>

#include <cstring>

const int N=507,inf=0x3f3f3f3f;

using namespace std;

int read() {

	int x=0,f=1;char s=getchar();

	for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

	for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

	return x*f;

}

int n,m,k,S,T,L[N],C[N],dis[N],mp[N][N],h[N],l[N];

struct node {

	int v,nxt,cap;

}e[2000007];

int head[2000007],tot=1;

void add(int u,int v,int cap) {

	e[++tot].v=v;

	e[tot].cap=cap;

	e[tot].nxt=head[u];

	head[u]=tot;

}

queue<int> q;

bool bfs() {

	memset(dis,-1,sizeof(dis));

	q.push(S);

	dis[S]=0;

	while(!q.empty()) {

		int u=q.front();

		q.pop();

		for(int i=head[u];i;i=e[i].nxt) {

			int v=e[i].v;

			if(dis[v]==-1&&e[i].cap) {

				dis[v]=dis[u]+1;

				q.push(v);

			}

		}

	}

	return dis[T]!=-1;

}

int dfs(int u,int f) {

	if(u==T) return f;

	int rest=f;

	for(int i=head[u];i;i=e[i].nxt) {

		int v=e[i].v;

		if(dis[v]==dis[u]+1&&e[i].cap&&rest) {

			int t=dfs(v,min(rest,e[i].cap));

			if(!t) dis[t]=0;

			e[i].cap-=t;

			e[i^1].cap+=t;

			rest-=t;

		}

	}

	return f-rest;

}

int dinic() {

	int ans=0;

	while(bfs()) ans+=dfs(S,inf);

	return ans;

}

int main() {

//	freopen("a.in","r",stdin);

	n=read(),m=read(),k=read();

	for(int i=1;i<=m;++i) L[i]=read();

	for(int i=1;i<=n;++i) C[i]=read();

	for(int i=1;i<=k;++i) {

		int x=read(),y=read();

		h[x]++,l[y]++;

		mp[x][y]=1;

	}

	for(int i=1;i<=n;++i) if(m-h[i]<L[i]) {puts("JIONG!");return 0;}

	for(int i=1;i<=m;++i) if(n-l[i]<C[i]) {puts("JIONG!");return 0;}

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j)

			if(!mp[i][j]) add(i,j+n,1),add(j+n,i,0);

	S=n+m+1,T=n+m+2;

	for(int i=1;i<=n;++i) add(S,i,m-h[i]-L[i]),add(i,S,0);

	for(int i=1;i<=m;++i) add(i+n,T,n-l[i]-C[i]),add(T,i+n,0);

	printf("%d\n",n*m-dinic()-k);

	return 0;

}