fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. const int MAX=20000+10;
  27. const int INF=10000000;
  28.  
  29. int n,m,a[MAX],b[MAX];
  30.  
  31. struct Edge
  32. {
  33. 	int s,t;
  34. 	int next;
  35. 	int res;
  36. }e[MAX*10];
  37. int nume,begin[MAX];
  38. int S,T;
  39.  
  40. void addedge(int a,int b,int c)
  41. {
  42. 	e[++nume].t=b;
  43. 	e[nume].s=a;
  44. 	e[nume].next=begin[a];
  45. 	begin[a]=nume;
  46. 	e[nume].res=c;
  47. }
  48.  
  49. void add(int a,int b,int c)
  50. {
  51. 	addedge(a,b,c);
  52. 	addedge(b,a,0);
  53. }
  54.  
  55. int gap[MAX],h[MAX];
  56. int tt=0;
  57.  
  58. int sap(int u,int flow)
  59. {
  60. 	if(u==T)
  61. 		return flow;
  62. 	++tt;
  63. 	if(tt>1000000)
  64. 		h[S]=T+1;
  65. 	int remain=flow,i,v;
  66. 	for(i=begin[u];i;i=e[i].next)
  67. 		if(h[v=e[i].t]+1==h[u] && e[i].res>0)
  68. 		{
  69. 			int tmp=sap(v,min(e[i].res,remain));
  70. 			e[i].res-=tmp;
  71. 			e[i^1].res+=tmp;
  72. 			remain-=tmp;
  73. 			if(!remain)
  74. 				return flow;
  75. 		}
  76. 	--gap[ h[u] ];
  77. 	if(!gap[h[u]])
  78. 		h[S]=T;
  79. 	++gap[++h[u]];
  80. 	return flow-remain;
  81. }
  82.  
  83. int check(int mid)
  84. {
  85. 	int i;
  86. 	S=n+m+1;
  87. 	T=n+m+2;
  88. 	nume=1;
  89. 	memset(begin,0,sizeof begin);
  90. 	memset(gap,0,sizeof gap);
  91. 	memset(h,0,sizeof h);
  92. 	gap[0]=T;
  93. 	REP(i,1,m)
  94. 	{
  95. 		add(S,i,1);
  96. 		add(i,a[i]+m,1);
  97. 		add(i,b[i]+m,1);
  98. 	}
  99. 	REP(i,1,n)
  100. 		add(i+m,T,mid);
  101. 	int ans=0;
  102. 	tt=0;
  103. 	while(h[S]<T)
  104. 		ans+=sap(S,INF);
  105. 	return (ans==m);
  106. }
  107.  
  108. int main()
  109. {
  110. //	freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  111. 	int i;
  112. 	scanf("%d%d",&n,&m);
  113. 	REP(i,1,m)
  114. 		scanf("%d%d",&a[i],&b[i]);
  115. 	if(!m)
  116. 	{
  117. 		printf("0\n");
  118. 		return 0;
  119. 	}
  120. 	int Left=0,Right=m;
  121. 	while(Left<Right)
  122. 	{
  123. 		int mid=(Left+Right)/2;
  124. 		if(!check(mid))
  125. 			Left=mid+1;
  126. 		else Right=mid;
  127. 	}
  128. 	check(Left);
  129. 	printf("%d\n",Left);
  130. 	REP(i,2,nume)
  131. 		if(e[i].t>m && e[i].t<=n+m && e[i].s<=m && i%2==0 && e[i].res==0)
  132. 			printf("%d\n",e[i].t-m==a[ e[i].s ]);
  133. 	return 0;
  134. }
  135.  
Success #stdin #stdout 0s 6860KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/m1Hquk
language:
C++ (gcc 8.3)
created:
10 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!