「BZOJ1458」士兵占领

2014年5月10日3,9970

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

题解

此题的思路是先放满棋盘，然后考虑最多可以删多少个。。。

某一行和某一列的可以放的格子数小于需求就直接jiong掉
然后从源向每一行连边,流量为可以放的格子数 – 需求的格子数(也就是可以删多少格子)
从每一列向汇,同上.
从每一个非障碍的格子的行向列连边流量为1
跑一遍最大流即可ans=可放格子数-maxflow

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define T 201
#define inf 0x7fffffff
inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    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;
}
using namespace std;
int n,m,K,cnt=1,tot,ans;
int l[105],c[105],a[105],b[105];
bool mp[105][105];
int q[205],h[205],head[205],cur[205];
struct data{int to,next,v;}e[100001];
void ins(int u,int v,int w)
{e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;}
void insert(int u,int v,int w)
{ins(u,v,w);ins(v,u,0);}
bool bfs()
{
    int t=0,w=1;
    for(int i=0;i<=T;i++)h[i]=-1;
    q[0]=0;h[0]=0;
    while(t!=w)
    {
        int now=q[t];t++;
        for(int i=head[now];i;i=e[i].next)
            if(e[i].v&&h[e[i].to]==-1)
            {
                h[e[i].to]=h[now]+1;
                q[w++]=e[i].to;
            }
    }
    if(h[T]==-1)return 0;
    return 1;
}
int dfs(int x,int f)
{
    if(x==T)return f;
    int w,used=0;
    for(int i=cur[x];i;i=e[i].next)
    {
        if(e[i].v&&h[e[i].to]==h[x]+1)
        {
            w=f-used;
            w=dfs(e[i].to,min(e[i].v,w));
            e[i].v-=w;
            if(e[i].v)cur[x]=i;
            e[i^1].v+=w;
            used+=w;if(used==f)return f;
        }
    }
    if(!used)h[x]=-1;
    return used;
}
void dinic()
{while(bfs()){for(int i=0;i<=T;i++)cur[i]=head[i];ans+=dfs(0,inf);}}
int main()
{
    m=read();n=read();K=read();
    int x,y;
	for(int i=1;i<=m;i++)
	    l[i]=n-read();
    for(int i=1;i<=n;i++)
        c[i]=m-read();
    for(int i=1;i<=K;i++)
    {
    	x=read();y=read();
    	mp[x][y]=1;
    	a[x]++;b[y]++;
    	if(a[x]>l[x]){printf("JIONG!");return 0;}
    	if(b[y]>c[y]){printf("JIONG!");return 0;}
    }
    tot=n*m-K;
    for(int i=1;i<=m;i++)
	    insert(0,i,l[i]-a[i]);
	for(int i=1;i<=n;i++)
	    insert(m+i,T,c[i]-b[i]); 
	for(int i=1;i<=m;i++)
	    for(int j=1;j<=n;j++)
	        if(!mp[i][j])insert(i,j+m,1);
    dinic();
    printf("%d",tot-ans);
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#define T 201

#define inf 0x7fffffff

inline int read()

{

char ch=getchar();

int f=1,x=0;

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;

}

using namespace std;

int n,m,K,cnt=1,tot,ans;

int l[105],c[105],a[105],b[105];

bool mp[105][105];

int q[205],h[205],head[205],cur[205];

struct data{int to,next,v;}e[100001];

void ins(int u,int v,int w)

{e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;}

void insert(int u,int v,int w)

{ins(u,v,w);ins(v,u,0);}

bool bfs()

{

int t=0,w=1;

for(int i=0;i<=T;i++)h[i]=-1;

q[0]=0;h[0]=0;

while(t!=w)

{

int now=q[t];t++;

for(int i=head[now];i;i=e[i].next)

if(e[i].v&&h[e[i].to]==-1)

{

h[e[i].to]=h[now]+1;

q[w++]=e[i].to;

}

if(h[T]==-1)return 0;

return 1;

}

int dfs(int x,int f)

{

if(x==T)return f;

int w,used=0;

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

{

if(e[i].v&&h[e[i].to]==h[x]+1)

{

w=f-used;

w=dfs(e[i].to,min(e[i].v,w));

e[i].v-=w;

if(e[i].v)cur[x]=i;

e[i^1].v+=w;

used+=w;if(used==f)return f;

}

if(!used)h[x]=-1;

return used;

}

void dinic()

{while(bfs()){for(int i=0;i<=T;i++)cur[i]=head[i];ans+=dfs(0,inf);}}

int main()

{

m=read();n=read();K=read();

int x,y;

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

l[i]=n-read();

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

c[i]=m-read();

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

{

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

mp[x][y]=1;

a[x]++;b[y]++;

if(a[x]>l[x]){printf("JIONG!");return 0;}

if(b[y]>c[y]){printf("JIONG!");return 0;}

}

tot=n*m-K;

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

insert(0,i,l[i]-a[i]);

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

insert(m+i,T,c[i]-b[i]);

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

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

if(!mp[i][j])insert(i,j+m,1);

dinic();

printf("%d",tot-ans);

return 0;

}

« 「JoyOI1517」飘飘乎居士的乌龟「BZOJ1711」[Usaco2007 Open] Dingin吃饭 »

hzwer.com _ Home | http://hzwer.com

「BZOJ1458」士兵占领

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论