士兵占领

发表于 | 分类于

题目

传送门
有一个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

OUTPUT

4

解题报告

也是很裸的网络流，所有行与源点连边，容量为Li，所有列与汇点连边，容量为Ci，可以放士兵的格子对应的行和列连边，跑最大流即为答案
要注意的是：点的坐标与数组大小的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
inline int read(){
    int sum(0);
    char ch(getchar());
    for(;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';sum=sum*10+ch-'0',ch=getchar());
    return sum;
}
struct edge{
    int s,e,w,n;
}a[50001];
int pre[250],tot;
inline void insert(int s,int e,int w){
    a[tot].s=s;
    a[tot].e=e;
    a[tot].w=w;
    a[tot].n=pre[s];
    pre[s]=tot++;
}
int n,m,k;
int sup;
int l[101],c[101];
bool g[101][101];
int sum(0);
int dis[301];
inline bool bfs(int s,int t){
	memset(dis,0,sizeof(dis));
	queue<int>q;
	q.push(s);
	dis[s]=1;
	while(!q.empty()){
		int k(q.front());
		q.pop();
	 	for(int i=pre[k];i!=-1;i=a[i].n){
			if(!a[i].w||dis[a[i].e])
				continue;
			dis[a[i].e]=dis[k]+1;
			if(a[i].e==t)
				return true;
			q.push(a[i].e);
        }
    }
    return false;
}
inline int my_min(int a,int b){
    return a<b?a:b;
}
inline int dfs(int now,int flow){
	if(now==sup)
		return flow;
	int tmp(flow),f;
	for(int i=pre[now];i!=-1;i=a[i].n){
		if(!a[i].w||!tmp||dis[a[i].e]!=dis[now]+1)
			continue;
		f=dfs(a[i].e,my_min(a[i].w,tmp));
		if(!f){
			dis[a[i].e]=0;
			continue;
		}
		a[i].w-=f;
		a[i^1].w+=f;
		tmp-=f;
	}
	return flow-tmp;
}
inline bool judge(){
    int tmp;
    for(int i=1;i<=m;i++){
        tmp=0;
        for(int j=1;j<=n;j++)
            if(g[i][j])
                tmp++;
        if(tmp<l[i])
            return true;
    }
    for(int j=1;j<=n;j++){
        tmp=0;
        for(int i=1;i<=m;i++)
            if(g[i][j])
                tmp++;
        if(tmp<c[j])
            return true;
    }
    return false;
}
int ans(0),inf(0x7fffffff);
int main(){
    memset(pre,-1,sizeof(pre));
    memset(g,true,sizeof(g));
    m=read(),n=read(),k=read();
    sup=n+m+1;
    for(int i=1;i<=m;i++)
        l[i]=read(),sum+=l[i];
    for(int i=1;i<=n;i++)
        c[i]=read(),sum+=c[i];
    for(int i=1;i<=k;i++){
        int x(read()),y(read());
        g[x][y]=0;
    }
    if(judge()){
        puts("JIONG!");
        return 0;
    }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(g[i][j])
                insert(i,j+m,1),insert(j+m,i,0);
    for(int i=1;i<=m;i++)
        insert(0,i,l[i]),insert(i,0,0);
    for(int i=1;i<=n;i++)
        insert(i+m,sup,c[i]),insert(sup,i+m,0);
    while(bfs(0,sup))
        ans+=dfs(0,inf);
    printf("%d",sum-ans);
    return 0;
}