题目描述
Bessie想驾驶她的飞船穿过危险的小行星群，小行星群是一个N×N的网格(1 <= N <= 500)，在网格内有K个小行星(1 <= K <= 10,000)。
幸运地是Bessie有一个很强大的武器，一次可以消除所有在一行或一列中的小行星，这种武器很贵，所以她希望尽量地少用。给出所有的小行星的位置，算出Bessie最少需要多少次射击就能消除所有的小行星。
输入
第1行：两个整数N和K，用一个空格隔开。
第2行至K+1行：每一行有两个空格隔开的整数R和C(1 <= R, C <= N)，分别表示小行星所在的行和列。
输出
1行：一个整数表示Bessie需要的最少射击次数，可以消除所有的小行星。
样例输入
3 4
1 1
1 3
2 2
3 2
样例输出
2
样例解释
【输入解释】：
下面的图表示上面的数据，”X”表示一个小行星，”.”表示为空：
X.X
.X.
.X.
【输出解释】：
Bessie在第1行射击消除在(1,1)和(1,3)上的小行星，在第2列射击消除在(2,2)和(3,2)上的小行星。
解法
网络流建模：
源点向所有行连一条容量为1的边，所有列向汇点连一条容量为1的边；
对于一个陨石(x,y)，把第x行向第y列连一条容量正无穷的边。
最小割即可。
检验：
可以花费1费用把任意一行或任意一列的与源点或汇点的边删掉，那么就可以使连接这行或这列的陨石的正无穷这条边无效化。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define sqr(x) ((x)*(x))
#define ln(x,y) int(log(x)/log(y))
#define row(x) (x+1)
#define col(x) (x+n+1)
#define po(x) (2*n+1+x)
using namespace std;
const char* fin="ex1922.in";
const char* fout="ex1922.out";
const int inf=0x7fffffff;
const int maxn=107*2,maxm=10007,maxtot=20007,maxr=maxtot*5;
int n,m,i,j,k,ans;
int fi[maxtot],la[maxr],ne[maxr],va[maxr];
int tot=1,num,bz[maxtot],card[maxtot];
int add_line(int a,int b,int c){
tot++;
ne[tot]=fi[a];
la[tot]=b;
va[tot]=c;
fi[a]=tot;
}
int add(int v,int u,int r){
add_line(v,u,r);
add_line(u,v,0);
}
int gap(int v,int flow){
int i,use=0,k;
if (v==num) return flow;
for (k=fi[v];k;k=ne[k])
if (va[k] && bz[v]==bz[la[k]]+1){
i=gap(la[k],min(va[k],flow-use));
use+=i;
va[k]-=i;
va[k^1]+=i;
if (flow==use || bz[1]==num) return use;
}
if (!--card[bz[v]]) bz[v]=num;
card[++bz[v]]++;
return use;
}
int main(){
scanf("%d%d",&n,&m);
num=n*2+2;
for (i=1;i<=m;i++){
scanf("%d%d",&j,&k);
add(row(j),col(k),inf);
}
for (i=1;i<=n;i++) add(1,row(i),1),add(col(i),num,1);
card[0]=num;
while (bz[1]<num) ans+=gap(1,inf);
printf("%d",ans);
return 0;
}启发
第一次网络流建模；
网络流中的任何一条边都可以看做使用容量费用来切掉，那么最小割可以灵活运用。
使用的SAP所用的优化
1.GAP优化，当任意距离的数量为0时，整个增广就不必继续增广。
2.当前弧优化，把当前所有的可增广的都增广。
3.使用异或优化编程复杂度，tot初始设为1，则k的反向弧就可以用k^1表示。