fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #define pp pair<int,int> >
  3. #define mp make_pair
  4. #define chk(a)	cout<<#a<<" : "<<a<<"\n";
  5. #define chk2(a,b) cout<<#a<<" : "<<a<<", "<<#b<<" : "<<b<<"\n";
  6. #define chk3(a,b,c) cout<<#a<<" : "<<a<<", "<<#b<<" : "<<b<<", "<<#c<<" : "<<c<<"\n";
  7. #define chk4(a,b,c,d) cout<<#a<<" : "<<a<<", "<<#b<<" : "<<b<<", "<<#c<<" : "<<c<<", "<<#d<<" : "<<d<<"\n";
  8. #define M 1000000007
  9. #define F first
  10. #define S second
  11. using namespace std;
  12. int n;
  13. int powe(int a,int b)
  14. {
  15. 	int ans=1;
  16. 	while(b)
  17. 	{
  18. 		if(b&1)
  19. 			ans=(ans*a)%M;
  20. 		b=b/2;
  21. 		a=(a*a)%M;
  22. 	}
  23. 	return ans;
  24. }
  25. int mini(int a,int b)
  26. {
  27.     if(a<b)
  28.         return a;
  29.         return b;
  30. }
  31. int gcde(int a,int b)
  32. {
  33. 	if(b==0)
  34. 		return a;
  35. 	return gcde(b,a%b);
  36. }
  37.  
  38. int cap[500008],flow[500008],gng[500008];//2*edges
  39. int d[100010];
  40. vector<int> gph[100010];
  41. int q[100010],ptr[100010];
  42. int id;
  43. void add_edge(int u,int v,int c)
  44. {
  45.         gng[id]=v,cap[id]=c,flow[id]=0;
  46.         gph[u].push_back(id);id++;
  47.         gng[id]=u,cap[id]=0,flow[id]=0;
  48.         gph[v].push_back(id);id++;
  49. }
  50. bool bfs()
  51. {
  52.     int u=1,to;
  53.     int fl,ca;
  54.     memset(d,-1,sizeof(d));
  55.  
  56.     d[1]=0;
  57.     int sx,ex;
  58.     sx=0;ex=-1;
  59.     q[++ex]=1;
  60.     while(sx<=ex and sx!=-1)
  61.     {
  62.         u=q[sx++];
  63.         for(int i=0;i<gph[u].size();i++)
  64.         {
  65.             int id=gph[u][i];
  66.             to=gng[id];
  67.             ca=cap[id];
  68.             fl=flow[id];
  69.             if(d[to]==-1 and ca-fl>0)
  70.             {
  71.                 d[to]=d[u]+1;
  72.                 q[++ex]=to;
  73.             }
  74.         }
  75.     }
  76.    // printf("d[n]=%d\n",d[n]);
  77.     return (d[n]!=-1);
  78. }
  79.  
  80. int dfs(int u,int fl)
  81. {
  82.     int to;
  83.     int ca,f;
  84.  
  85.     if(u==n)
  86.         return fl;
  87.    // chk(u);
  88.  
  89.     for(;ptr[u]<gph[u].size();++ptr[u])
  90.     {
  91.  
  92.         int id=gph[u][ptr[u]];
  93.         to=gng[id];
  94.         ca=cap[id];
  95.         f=flow[id];
  96.  
  97.         if(ca-f>0 and d[to]==d[u]+1)
  98.         {
  99.             fl=mini(fl,ca-f);
  100.             int df=dfs(to,fl);
  101.             if(df>0)
  102.             {
  103.  
  104.                 flow[id]+=df;
  105.                 flow[id^1]-=df;
  106.                 return df;
  107.             }
  108.         }
  109.     }
  110.     return 0;
  111. }
  112. int main()
  113. {
  114.     int m,i,u,v,c,cw,bl,j;
  115.     scanf("%d%d%d",&cw,&bl,&m);
  116.     n=cw+bl+2;
  117.  
  118.     for(i=1;i<=cw;i++)
  119.         add_edge(1,i+1,1);
  120.     for(i=1;i<=bl;i++)
  121.         add_edge(cw+1+i,n,1);
  122.  
  123.     for(i=0;i<m;i++)
  124.     {
  125.         scanf("%d%d",&u,&v);
  126.         add_edge(1+u,1+cw+v,1);
  127.  
  128.     }
  129.         int ans=0;
  130.         while(bfs())
  131.         {
  132.             memset(ptr,0,sizeof(ptr));
  133.             while(true)
  134.             {
  135.                 int df=dfs(1,1e15);
  136.                 if(df==0)
  137.                     break;
  138.                 ans+=df;
  139.             }
  140.         }
  141.         printf("%d\n",ans);
  142.         return 0;
  143. }
  144.  
Success #stdin #stdout 0s 11672KB
comments (?)
stdin
copy 
34 429
14 1
15 2
27 4
31 5
14 6
26 7
31 8
3 9
12 10
24 11
3 12
3 13
3 14
3 15
20 16
29 17
12 18
29 19
15 20
16 21
14 22
8 23
15 24
6 25
12 26
19 27
21 28
15 29
3 30
14 31
24 32
29 33
2 34
15 1
9 12
19 30
4 18
29 5
17 13
8 18
19 24
11 21
26 22
21 20
27 9
4 22
29 2
19 6
1 17
21 22
26 21
20 27
32 29
33 1
2 18
15 19
1 3
28 14
16 10
1 19
18 24
16 24
30 18
13 10
9 32
30 27
7 4
15 18
25 12
31 21
9 2
27 31
16 8
5 30
24 20
25 34
33 4
27 10
23 21
21 27
24 26
11 22
23 33
16 7
5 9
11 10
4 16
20 26
26 5
14 2
8 25
30 10
26 33
12 24
33 9
15 7
30 24
7 10
9 30
33 13
26 29
20 18
19 23
20 12
34 19
29 25
12 34
22 33
34 31
2 28
13 22
11 26
13 18
8 9
10 1
6 9
11 15
32 34
14 19
24 13
17 2
22 3
34 14
18 25
32 26
28 4
19 18
34 3
5 20
13 32
17 28
17 14
24 21
10 17
27 3
1 7
26 14
22 27
8 33
27 17
14 13
2 20
2 10
11 6
1 32
16 22
30 17
34 1
27 2
29 16
16 9
32 6
30 23
22 18
13 7
2 26
31 13
6 1
15 32
18 23
5 2
20 22
15 23
5 12
6 34
32 31
11 23
20 3
34 28
5 21
21 1
9 23
8 14
27 24
4 11
23 17
31 16
10 25
9 26
7 14
18 5
28 33
5 17
19 25
13 28
26 6
16 19
11 31
5 10
11 1
20 19
9 14
17 22
18 14
30 7
26 3
7 9
21 8
28 27
1 23
33 12
7 3
9 21
17 31
8 15
6 3
25 31
26 30
5 8
12 16
12 32
9 31
8 13
20 13
30 31
23 29
5 15
7 8
28 19
15 27
29 34
17 15
21 25
22 24
33 24
10 28
31 23
23 28
31 28
15 26
13 15
11 9
30 8
1 22
32 25
6 29
32 8
2 22
28 25
23 4
5 16
31 24
2 33
32 10
1 28
18 33
7 24
2 1
13 4
4 21
18 9
16 3
10 22
26 1
34 13
34 8
27 34
25 23
12 28
4 8
25 27
5 19
28 18
12 17
31 22
18 3
1 13
22 5
24 28
29 12
10 20
6 10
22 29
17 21
6 33
26 31
10 19
33 31
12 11
31 20
7 28
12 15
2 31
33 3
24 4
13 12
20 9
14 16
11 7
11 32
32 27
34 30
23 32
34 15
24 5
22 7
15 6
31 12
6 7
6 8
24 1
25 1
34 23
31 15
20 7
29 4
28 8
14 24
22 12
18 17
11 13
21 15
14 10
18 1
22 28
33 34
17 32
29 11
6 31
4 32
14 21
12 23
15 4
17 20
34 17
5 1
34 20
13 29
23 13
27 6
2 3
19 7
31 7
26 8
8 1
30 12
21 2
1 29
18 11
10 33
6 5
33 21
30 21
7 5
32 5
26 28
17 16
16 11
4 3
28 3
21 6
14 11
29 3
16 33
10 26
31 10
33 30
12 2
23 3
10 23
5 4
6 13
24 9
21 34
16 23
14 5
31 3
17 24
34 26
22 23
2 19
32 28
13 27
21 12
24 23
28 20
21 7
15 25
9 34
29 30
1 4
14 20
15 30
11 25
13 25
32 3
13 9
16 28
2 7
23 20
7 32
12 6
6 24
13 2
10 34
27 5
27 16
19 26
1 9
19 12
19 13
17 6
34 22
15 33
11 19
6 30
20 32
4 26
17 7
21 10
30 22
4 14
17 3
18 16
22 6
24 3
27 1
23 14
32 30
10 15
9 4
21 18
2 25
12 1
21 3
21 13
4 10
8 11
18 6
stdout
copy 
9
https://ideone.com/nESKzq
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!