题目: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;
}
网友评论