[Luogu1345][USACO5.4]Telecowmunication 最大流

题目链接：https://www.luogu.org/problem/show?pid=1345

求最小割点集的大小，直接拆点转化成最小割边。把一个点拆成出点入点，入点向出点连一条容量为1的边，其他的边容量无穷大。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int INF=1<<30;
 6 int inline readint(){
 7     int Num;char ch;
 8     while((ch=getchar())<'0'||ch>'9');Num=ch-'0';
 9     while((ch=getchar())>='0'&&ch<='9') Num=Num*10+ch-'0';
10     return Num;
11 }
12 int N,M,S,T;
13 int to[3000],ne[3000],c[3000],fir[210],cnt=0;
14 void Add(int x,int y,int z){
15     to[cnt]=y;
16     c[cnt]=z;
17     ne[cnt]=fir[x];
18     fir[x]=cnt++;
19     to[cnt]=x;
20     c[cnt]=0;
21     ne[cnt]=fir[y];
22     fir[y]=cnt++;
23 }
24 int dep[210],bfn[210],ti=0;
25 int q[210],head,tail;
26 bool Bfs(){
27     head=tail=1;
28     q[1]=S;
29     dep[S]=1;
30     bfn[S]=++ti;
31     while(head<=tail){
32         int u=q[head++];
33         for(int i=fir[u];i!=-1;i=ne[i]){
34             int v=to[i];
35             if(bfn[v]!=ti&&c[i]){
36                 bfn[v]=ti;
37                 dep[v]=dep[u]+1;
38                 q[++tail]=v;
39             }
40         }
41     }
42     return bfn[T]==ti;
43 }
44 int cur[210];
45 int Dfs(int u,int maxf){
46     if(u==T||!maxf) return maxf;
47     int flow=0,f;
48     for(int &i=cur[u];i!=-1;i=ne[i]){
49         int v=to[i];
50         if(dep[v]==dep[u]+1&&(f=Dfs(v,min(maxf,c[i])))>0){
51             flow+=f,maxf-=f;
52             c[i]-=f,c[i^1]+=f;
53             if(!maxf) break;
54         }
55     }
56     return flow;
57 }
58 int Dinic(){
59     int ans=0;
60     while(Bfs()){
61         memcpy(cur,fir,sizeof(fir));
62         ans+=Dfs(S,INF);
63     }
64     return ans;
65 }
66 int main(){
67     N=readint();
68     M=readint();
69     S=readint();
70     T=readint();
71     memset(fir,-1,sizeof(fir));
72     for(int i=1;i<=M;i++){
73         int a=readint(),
74             b=readint();
75         Add(a+N,b,INF);
76         Add(b+N,a,INF);
77     }
78     for(int i=1;i<=N;i++) Add(i,i+N,1);
79     Add(S,S+N,INF);
80     printf("%d
",Dinic());
81     return 0;
82 }