没人写 Dinic ，我就来一篇吧
1.题意
对于每一个行星，要么选该行，要么选该列。
是不是有点熟悉？
2.分析
没错，他就是二分图最小点覆盖。
我的算法是将二分图转化为网络流，再跑一遍最小割。
即将左边的点与 $s$ 连接，右边的点与 $t$ 连接，权值均为1（代价为1）。
中间的边，权值 $+\infty$ （这样就不会成为割边了）。
证明：割与点覆盖一一对应
对于每一个割，左边与源点如果满流，则选取；右边同理。
由于是割， $s$ 到 $t$ 不经过满流的点，就无法到达（否则又有了增广路）。
所以所有的边都被覆盖了，否则 $s$ 可以到 $t$，与割的定义矛盾。
对于每一个点覆盖，左边与源点连边满流；右边同理。
这时，由于中间的边都被覆盖了，$s$ 无法到 $t$。
所以这就是一个割。
证毕
又由最小割最大流定理可得：最小割=最大流。
那么，直接 Dinic 就可以了。
不懂网络流的同学，请移步
我的博客 或百度 逃
Code：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
using namespace std;
int h[N],e[M],ne[M],w[M],idx,S,T;
int cur[N],q[N],d[N];
int n,m;
void add(int a,int b,int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
e[idx]=a,ne[idx]=h[b],w[idx]=0,h[b]=idx++;
}
inline void read(int &res)
{
char c;
while (!isdigit(c=getchar()));
res=c-'0';
while (isdigit(c=getchar())) res=(res<<1)+(res<<3)+c-'0';
return;
}
bool bfs()
{
memset(d,0,sizeof d);
int hh=1,tt=1;
q[1]=S;cur[S]=h[S];d[S]=1;
while (hh<=tt)
{
int x=q[hh++];
for (int i=h[x];~i;i=ne[i])
if (!d[e[i]]&&w[i])
{
d[e[i]]=d[x]+1;
cur[e[i]]=h[e[i]];
if (e[i]==T) return true;
q[++tt]=e[i];
}
}
return false;
}
int findflow(int x,int limit)
{
if (x==T) return limit;
int flow=0;
for (int i=cur[x];~i&&flow<limit;i=ne[i])
{
cur[x]=i;
if (d[e[i]]==d[x]+1&&w[i])
{
int t=findflow(e[i],min(w[i],limit-flow));
if (!t) d[e[i]]=-1;
w[i]-=t,w[i^1]+=t,flow+=t;
}
}
return flow;
}
int dinic()
{
int r=0,flow;
while (bfs()) while (flow=findflow(S,INF)) r+=flow;
return r;
}
int main()
{
memset(h,-1,sizeof h);
read(n);read(m);
int a,b;
S=0,T=2*n+1;
while (m--)
{
read(a);read(b);
add(a,b+n,INF);
}
for (int i=1;i<=n;++i) add(S,i,1);
for (int i=1;i<=n;++i) add(i+n,T,1);
printf("%d\n",dinic());
return 0;
}