bzoj1458 士兵占据

1458: 士兵占据

Time Limit: 10 Sec Memory Limit: 64 MB

Submit: 685 Solved: 398

[Submit][Status][

id=1458" style="color:blue; text-decoration:none">Discuss]

Description

有一个M * N的棋盘，有的格子是障碍。如今你要选择一些格子来放置一些士兵，一个格子里最多能够放置一个士兵，障碍格里不能放置士兵。我们称这些士兵占据了整个棋盘当满足第i行至少放置了Li个士兵, 第j列至少放置了Cj个士兵。如今你的任务是要求使用最少个数的士兵来占据整个棋盘。

Input

第一行两个数M, N, K分别表示棋盘的行数，列数以及障碍的个数。第二行有M个数表示Li。第三行有N个数表示Ci。

接下来有K行，每行两个数X, Y表示(X, Y)这个格子是障碍。

Output

输出一个数表示最少须要使用的士兵个数。

假设不管放置多少个士兵都没有办法占据整个棋盘，输出”JIONG!” (不含引號)

Sample Input

4 4 4

1 1 1 1

0 1 0 3

1 4

2 2

3 3

4 3

Sample Output

4

数据范围

M, N <= 100, 0 <= K <= M * N

HINT

Source

有源汇有上下界最小流问题

将行抽象为左部点，列抽象为右部点。

假设某个位置没有障碍。就从行相应的节点到列相应的节点连边。下界为0，上界为1。

在从源点向每行相应的节点连边，从每列相应的节点向汇点连边，下界均为该行或列的最少士兵数。上界均为正无穷。

最后求s到t的最小流。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<algorithm>

#include<queue>

#define F(i,j,n) for(int i=j;i<=n;i++)

#define D(i,j,n) for(int i=j;i>=n;i--)

#define ll long long

#define pa pair<int,int>

#define maxn 300

#define maxm 100000

#define inf 1000000000

using namespace std;

int head[maxn],cur[maxn],dis[maxn],in[maxn];

int cnt=1,mx=0,maxflow,n,m,k,x,y,s,t,ss,tt;

bool a[105][105];

struct edge_type

{

	int next,to,v;

}e[maxm];

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;

}

inline void add_edge(int x,int y,int v)

{

	e[++cnt]=(edge_type){head[x],y,v};head[x]=cnt;

	e[++cnt]=(edge_type){head[y],x,0};head[y]=cnt;

}

inline void insert(int x,int y,int l,int r)

{

	in[x]-=l;in[y]+=l;

	if (r-l) add_edge(x,y,r-l);

}

inline void build()

{

	F(i,1,tt)

	{

		if (in[i]>0) add_edge(ss,i,in[i]);

		else if (in[i]<0) add_edge(i,tt,-in[i]);

	}

}

inline bool bfs()

{

	queue<int>q;

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

	dis[s]=0;q.push(s);

	while (!q.empty())

	{

		int tmp=q.front();q.pop();

		if (tmp==t) return true;

		for(int i=head[tmp];i;i=e[i].next) if (e[i].v&&dis[e[i].to]==-1)

		{

			dis[e[i].to]=dis[tmp]+1;

			q.push(e[i].to);

		}

	}

	return false;

}

inline int dfs(int x,int f)

{

	if (x==t) return f;

	int tmp,sum=0;

	for(int &i=cur[x];i;i=e[i].next)

	{

		int y=e[i].to;

		if (e[i].v&&dis[y]==dis[x]+1)

		{

			tmp=dfs(y,min(f-sum,e[i].v));

			e[i].v-=tmp;e[i^1].v+=tmp;sum+=tmp;

			if (sum==f) return sum;

		}

	}

	if (!sum) dis[x]=-1;

	return sum;

}

inline void dinic()

{

	maxflow=0;

	while (bfs())

	{

		F(i,1,tt) cur[i]=head[i];

		maxflow+=dfs(s,inf);

	}

}

inline void minflow()

{

	s=ss;t=tt;

	dinic();

	int ans=e[cnt].v;

	if (ans<mx)

	{

		printf("JIONG!\n");

		return;

	}

	e[cnt].v=e[cnt^1].v=0;

	s=n+m+2;t=n+m+1;

	dinic();

	printf("%d\n",ans-maxflow);

}

int main()

{

	int tot=0;

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

	s=m+n+1;t=s+1;ss=t+1;tt=ss+1;

	F(i,1,m){x=read();tot+=x;insert(s,i,x,inf);}

	mx=max(mx,tot);

	tot=0;

	F(i,1,n){x=read();tot+=x;insert(i+m,t,x,inf);}

	mx=max(mx,tot);

	F(i,1,k)

	{

		x=read();y=read();

		a[x][y]=true;

	}

	F(i,1,m) F(j,1,n) if (!a[i][j]) insert(i,j+m,0,1);

	build();

	add_edge(t,s,inf);

	minflow();

}

巴特西