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
| const int N=12000+96;
struct edge{int to,nxt,w;}e[N*2];int hd[N],cur[N],tot=1;
void add(int u,int v,int w){
e[++tot]=(edge){v,hd[u],w}; hd[u]=tot;
}
int n,m,s,su,lv[N];
int bfs(){
memset(lv,0,sizeof(lv));
memcpy(cur, hd, sizeof(hd));
queue<int> q;
q.push(s);
lv[s]=1;
while(!q.empty()){
int p=q.front();
q.pop();
for(int eg=hd[p];eg;eg=e[eg].nxt){
int to=e[eg].to,vol=e[eg].w;
if(vol&&!lv[to]){
lv[to]=lv[p]+1,q.push(to);
}
}
}
return lv[n];
}
int dfs(int p,int flow){
if(p==n)
return flow;
int r=flow;
for (int eg = cur[p]; eg && r; eg = e[eg].nxt){
cur[p]=eg;
int to = e[eg].to, vol = e[eg].w;
if(vol&&lv[to]==lv[p]+1){
int c=dfs(to,min(r,vol));
r-=c;
e[eg].w-=c;
e[eg^1].w+=c;
}
}
return flow-r;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>su>>m>>s>>n;
s+=su;
f(i,1,su)
{
add( i, i+su, 1 ) ; add( i+su, i, 0 ) ;
}
f(i,1,m){
int aa,bb;
cin>>aa>>bb;
add(aa+su,bb,1);
add(bb,aa+su,0);
add(bb+su,aa,1);
add(aa,bb+su,0);
}
LL ans=0;
while(bfs()){
ans+=dfs(s,3e8);
}
cout<<ans;
return 0;
}
|