Tony Zhao

题目大意

给你一个$n*m$的棋盘，有的格子不可用，请在可用位置放置最少的士兵使得棋盘的第$i$行至少有$l_i$个士兵，第$i$列有$c_i$个士兵。

行向列连边，边权为1，S向行连边，边权为$l_i$，列向T连边，边权为$c_i$.

一种方法是求有上下界最小流，另一种方法是求最小费用最大流。

都能过，但是有上下界最小流速度比最小费用最大流快到不知到哪里去了。

最小流

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF (1<<30)
int m,n,k,S,T,SS,TT,du[300],depth[300],ans;
bool v[110][110];
queue<int>q;
int to[500000],nxt[500000],val[500000],head[300],tot=1;
inline void AE(int x,int y,int z)
{
	to[++tot]=y,nxt[tot]=head[x],head[x]=tot,val[tot]=z;
	to[++tot]=x,nxt[tot]=head[y],head[y]=tot,val[tot]=0;
}
bool BFS(int x,int y)
{
	while(!q.empty()) q.pop();
	q.push(x);
	memset(depth,-1,sizeof depth),depth[x]=0;
	while(!q.empty())
	{
		int tmp=q.front();q.pop();
		for(int i=head[tmp];i;i=nxt[i])
			if(val[i]&&depth[to[i]]==-1)
			{
				depth[to[i]]=depth[tmp]+1;
				if(to[i]==y) return true;
				q.push(to[i]);
			}
	}
	return false;
}
int dinic(int pos,int tgt,int left)
{
	if(pos==tgt) return left;
	int nleft=left;
	for(int i=head[pos];i;i=nxt[i])
		if(val[i]&&depth[to[i]]==depth[pos]+1)
		{
			int tmp=dinic(to[i],tgt,min(nleft,val[i]));
			if(!tmp) depth[to[i]]=-1;
			nleft-=tmp,val[i]-=tmp,val[i^1]+=tmp;
			if(!nleft) break;
		}
	return left-nleft;
}
int main()
{
	int tmp,tx,ty;
	scanf("%d%d%d",&m,&n,&k),S=0,T=n+m+1,SS=n+m+2,TT=n+m+3;
	for(int i=1;i<=m;++i) scanf("%d",&tmp),du[S]-=tmp,du[i]+=tmp,AE(S,i,INF-tmp);
	for(int i=1;i<=n;++i) scanf("%d",&tmp),du[m+i]-=tmp,du[T]+=tmp,AE(m+i,T,INF-tmp);
	while(k--) scanf("%d%d",&tx,&ty),v[tx][ty]=true;
	for(int i=1;i<=m;++i)
		for(int j=1;j<=n;++j)
			if(!v[i][j])
				AE(i,m+j,1);
	for(int i=0;i<=n+m+1;++i)
	{
		if(du[i]>0) AE(SS,i,du[i]);
		if(du[i]<0) AE(i,TT,-du[i]);
	}
	AE(T,S,INF);
	while(BFS(SS,TT)) ans+=dinic(SS,TT,INF);
	for(int i=0;i<=n+m+1;++i) if(du[i]>0) ans-=du[i];
	if(ans!=0) puts("JIONG!");
	else
	{
		ans=val[tot],val[tot]=val[tot-1]=0;
		for(int i=head[SS];i;i=nxt[i]) val[i]=val[i^1]=0;
		for(int i=head[TT];i;i=nxt[i]) val[i]=val[i^1]=0;
		while(BFS(T,S)) ans-=dinic(T,S,INF);
		printf("%d\n",ans);
	}
	return 0;
}

最小费用最大流

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int m,n,k,S=0,T=299,l[300],c[300],depth[300],dis[300],frm[300],pre[300],ans;
bool bad[110][110];
int to[500000],nxt[500000],val[500000],cst[500000],head[300],tot=1;
queue<int>q;
inline void AE(int x,int y,int a,int b)
{
	to[++tot]=y,nxt[tot]=head[x],head[x]=tot,val[tot]=a,cst[tot]=b;
	to[++tot]=x,nxt[tot]=head[y],head[y]=tot,val[tot]=0,cst[tot]=-b;
}
bool SPFA()
{
	q.push(S);
	memset(dis,0x3f,sizeof dis),dis[S]=0;
	frm[T]=-1;
	while(!q.empty())
	{
		int tmp=q.front();q.pop();
		for(int i=head[tmp];i;i=nxt[i])
			if(val[i]&&dis[to[i]]>dis[tmp]+cst[i])
			{
				dis[to[i]]=dis[tmp]+cst[i];
				frm[to[i]]=tmp,pre[to[i]]=i;
				q.push(to[i]);
			}
	}
	return ~frm[T];
}
int main()
{
	int tmp,tx,ty;
	scanf("%d%d%d",&m,&n,&k);
	for(int i=1;i<=m;++i) scanf("%d",l+i),AE(S,i,l[i],0);
	for(int i=1;i<=n;++i) scanf("%d",c+i),AE(m+i,T,c[i],0);
	for(int i=1;i<=k;++i) scanf("%d%d",&tx,&ty),bad[tx][ty]=true;
	for(int i=1;i<=m;++i)
	{
		tmp=0;
		for(int j=1;j<=n;++j) if(!bad[i][j]) tmp++;
		if(tmp<l[i]) puts("JIONG!"),exit(0);
	}
	for(int j=1;j<=n;++j)
	{
		tmp=0;
		for(int i=1;i<=m;++i) if(!bad[i][j]) tmp++;
		if(tmp<c[j]) puts("JIONG!"),exit(0);
	}
	for(int i=1;i<=m;++i) for(int j=1;j<=n;++j) if(!bad[i][j]) AE(i,m+j,1,1);
	while(SPFA())
	{
		ans++;
		for(int i=T;i!=S;i=frm[i]) val[pre[i]]--,val[pre[i]^1]++;
	}
	printf("%d\n",ans);
	return 0;
}

BZOJ 1458 士兵占领

题目大意