BZOJ-1458: 士兵占领（网络流）

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1458

这道题我开始没有想出来，后来是在群上ORZ了某大神之后才知道可以用二分图匹配写的。（刚开始是用不等式消元建图写得快吐，后来果断放弃）做法如下：

把每一行和每一列看成一个点，然后源点连每个行，容量为该行可行的格子数-需要的士兵数，每列连汇，容量为该列可行的格子数-需要的士兵数，然后对于每个可行点(i,j)行i连列j，容量1。跑一次最大流，用总可行格子数-流就是答案。

代码：

c83d70cf3bc79f3d7cdeea3fb8a1cd11728b2985.jpg.png

#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
#define MAXN 110
#define MAXV 310
#define clear(x) memset(x,0,sizeof(x))
#define rep(i,x) for (int i=0;i++<x;)
#define inf 0x7fffffff
 
struct edge {
    edge *pair,*next;
    int t,f;
    edge () {
        next=pair=NULL;
    }
} *head[MAXV];
 
void Add(int s,int t,int f) {
    edge *p=new(edge);
    p->t=t,p->next=head[s],p->f=f;
    head[s]=p;
}
 
void AddEdge(int s,int t,int f) {
    Add(s,t,f),Add(t,s,0);
    head[s]->pair=head[t],head[t]->pair=head[s];
}
 
int S,T,n,m,k,sumn[MAXN],summ[MAXN],l[MAXN],r[MAXN],sum;
bool f[MAXN][MAXN];
 
edge *d[MAXV];
int h[MAXV],gap[MAXV];
 
int sap(int v,int flow) {
    if (v==T) return flow;
    int rec=0;
    for (edge *p=d[v];p;p=p->next) if (p->f&&h[v]==h[p->t]+1) {
        int ret=sap(p->t,min(flow-rec,p->f));
        p->f-=ret,p->pair->f+=ret,d[v]=p;
        if ((rec+=ret)==flow) return flow;
    }
    if (!(--gap[h[v]])) h[S]=T;
    gap[++h[v]]++,d[v]=head[v];
    return rec;
}
 
int maxflow() {
    clear(gap),clear(h);
    gap[0]=T;
    rep(i,T) d[i]=head[i];
    int flow=0;
    while (h[S]<T) flow+=sap(S,inf);
    return flow;
}
 
int main() {
    clear(sumn),clear(summ),clear(head);
    memset(f,true,sizeof(f));
    scanf("%d%d%d",&n,&m,&k);
    sum=n*m-k;
    rep(i,n) scanf("%d",&l[i]);
    rep(i,m) scanf("%d",&r[i]);
    while (k--) {
        int x,y;
        scanf("%d%d",&x,&y);
        sumn[x]++,summ[y]++,f[x][y]=false;
    }
    rep(i,n) if (sumn[i]+l[i]>m) {
        printf("JIONG!\n");
        return 0;
    }
    rep(i,m) if (summ[i]+r[i]>n) {
        printf("JIONG!\n");
        return 0;
    }
    S=n+m+1,T=n+m+2;
    rep(i,n) AddEdge(S,i,m-sumn[i]-l[i]);
    rep(i,m) AddEdge(n+i,T,n-summ[i]-r[i]);
    rep(i,n) rep(j,m) if (f[i][j]) AddEdge(i,n+j,1);
    printf("%d\n",sum-maxflow());
    return 0;
}