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

 

solution：

首先 JIONG! 很好判断的：如果某一行/列的 要求数>行/列总数-障碍数，则是 JIONG!

由于 横行只能放Li个  竖行只能放Ci个 

源点S 向各横行连边，容量为Li

汇点T 向各竖行连边，容量为Ci  (因为不是JIONG!，一定能放下，所以限制最少)

如果横行和竖行交点无障碍，连一条容量为 1 的边

1 #include
       
          2 #include
        
           3 #include
         
            4 #define mem(a,b) memset(a,b,sizeof(a))  5 using namespace std;  6 const int INF=(1<<31)-1;  7 inline int minn(int a,int b){
     return a
          
           =he?0:1;} 35 inline void push(int x){dui[++en]=x;} 36 inline void pop(){++he;} 37 inline int top(){
     return dui[he];} 38  39 int bfs() 40 { 41     mem(dep,0); 42     clear(); 43     dep[S]=1;push(S); 44     while(!empty()) 45     { 46         int now=top();pop(); 47         for(int i=first[now];i!=-1;i=a1[i].next) 48         { 49             int temp=a1[i].v; 50             if(dep[temp]||!a1[i].w)continue; 51             dep[temp]=dep[now]+1; 52             push(temp); 53             if(temp==T)return 1; 54         } 55     } 56     return 0; 57 } 58  59 int dfs(int x,int val) 60 { 61     if(x==T)return val; 62     int val2=val,k; 63     for(int i=first[x];i!=-1;i=a1[i].next) 64     { 65         int temp=a1[i].v; 66         if(dep[temp]!=dep[x]+1||!a1[i].w||!val2)continue; 67         k=dfs(temp,minn(val2,a1[i].w)); 68         if(!k){dep[temp]=0;continue;} 69         a1[i].w-=k;a1[i^1].w+=k;val2-=k; 70     } 71     return val-val2; 72 } 73  74 int Dinic() 75 { 76     int ans=0; 77     while(bfs()) 78       ans+=dfs(S,INF); 79     return ans; 80 } 81  82 int main(){ 83     int flag=0; 84     mem(first,-1); 85     scanf("%d%d%d",&n,&m,&k); 86     S=0;T=n+m+1; 87     for(int i=1;i<=n;++i) 88     {scanf("%d",&heng[i]);sum+=heng[i];} 89     for(int i=1;i<=m;++i) 90     {scanf("%d",&shu[i]);sum+=shu[i];} 91      92     for(int i=1;i<=k;++i) 93     {scanf("%d%d",&u,&o);ji[u][o]=1;++num1[u];++num2[o];} 94      95     for(int i=1;i<=n;++i)if(m-num1[i]