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
89
90
91
92
93
94
95
96
|
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
long long read()
{
long long x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int N=200+10;
const int inf=0x3f3f3f3f;
struct road
{
int to,w,rev;
road (int A,int B,int C)
{
to=A,w=B,rev=C;
}
};
vector <road> e[N];
int n,m,c1,c2,depth[N];
queue <int> dl;
bool bfs()
{
memset(depth,0,sizeof depth);
depth[c1]=1;
dl.push(c1);
while(dl.empty()==false)
{
int now=dl.front();
dl.pop();
for(int i=0;i<int(e[now].size());i++)
if(e[now][i].w>0 and depth[e[now][i].to]==0)
{
depth[e[now][i].to]=depth[now]+1;
dl.push(e[now][i].to);
}
}
if(depth[c2]==0) return false;
return true;
}
int dfs(int now,int f)
{
if(now==c2) return f;
int ans=0;
for(int i=0;i<int(e[now].size());i++)
if(e[now][i].w>0 and depth[e[now][i].to]==depth[now]+1)
{
int temp=dfs(e[now][i].to,min(f,e[now][i].w));
e[now][i].w-=temp;
e[e[now][i].to][e[now][i].rev].w+=temp;
f-=temp,ans+=temp;
if(f==0) break;
}
return ans;
}
int Dinic()
{
int ans=0;
while(bfs()==true)
ans+=dfs(c1,inf);
return ans;
}
inline void AddLine(int s,int t,int w)
{
e[s].push_back(road(t,w,e[t].size()));
e[t].push_back(road(s,0,e[s].size()-1));
}
int main()
{
n=read(),m=read(),c1=read(),c2=read();
for(int i=1;i<=n;i++) e[i].reserve(8);
for(int i=1;i<=n;i++)
if(i==c1 or i==c2)
AddLine(i,i+n,inf);
else
AddLine(i,i+n,1);
for(int i=1;i<=m;i++)
{
int s=read(),t=read();
AddLine(s+n,t,inf);
AddLine(t+n,s,inf);
}
printf("%d",Dinic());
return 0;
}
|
红色的边边权为1，黑色的边边权为inf。 原点和汇点的内部边权为inf，因为显然这两个点不能删除。 题面给的边删除没意义（因为我们要删点），所以也设为inf(事实上设为1也没问题，因为删除这条边的权值可以理解为删除了一个点) 至于怎么算割边，可以证明割边在数值上等于最大流（本蒟蒻不会证） 至于怎么求最大流…可以参考这个博客 最后记得双倍空间 然后就OjbK了
