fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int Long;
  4. typedef long long int ll;
  5. //typedef int ll;
  6. typedef ll ft;
  7. typedef set<int> si;
  8. typedef long long Long;
  9. typedef vector<int> vi;
  10. typedef vector<vi> vii;
  11. typedef vector<Long>vl;
  12. typedef pair<int,int>pii;
  13. typedef pair<Long,Long>pll;
  14. typedef pair<string,int>psi;
  15. typedef pair<double,double>pdd;
  16. #define get getchar_unlocked
  17. #define put putchar_unlocked
  18. #define pb push_back
  19. #define mp make_pair
  20. #define ff first
  21. #define ss second
  22. #define sz size()
  23. #define ln length()
  24. #define repstl(i, s) for (__typeof((s).end())i=(s).begin();i!=(s).end();++i)
  25. #define debug1(s,a) cout << s << " " << a << " " << endl;
  26. #define debug2(s,a,b) cout << s << " " << a << " " << b << " " << endl
  27. #define debug3(s,a,b,c) cout << s << " " << a << " " << b << " " << c << " " << endl;
  28. #define debug4(s,a,b,c,d) cout << s << " " << a << " " << b << " " << c << " " << d << " " << endl;
  29. #define debug5(s,a,b,c,d,e) cout << s << " " << a << " " << b << " " << c << " " << d << " " << e << " " << endl;
  30. #define PI 3.1415926535897932384626433832795
  31. #define FO freopen ("out.txt", "w", stdout)
  32. #define FI freopen ("in.txt", "r", stdin)
  33. #define ref(i,a,n) for(int i=a;i<=n;i++)
  34. #define reb(i,n,a) for(int i=n;i>=a;i--)
  35. #define rep(i,n) for(int i=0;i<n;i++)
  36. #define all(a) a.begin(),a.end()
  37. #define gi(n) scanf("%d",&n)
  38. #define gii(n) scanf("%lld",&n)
  39. #define gc(c) scanf(" %c",&c)
  40. #define gs(s) scanf(" %s",s);
  41. #define pi(n) printf("%d",n)
  42. #define pii(n) printf("%lld",n)
  43. #define pc(c) printf("%c",c)
  44. #define ps printf(" ")
  45. #define pn printf("\n")
  46. #define pl(a) printf("%s",a)
  47. #define l(a) 2*a+1
  48. #define r(a) 2*a+2
  49. #define left(a,b) a,(a+b)/2
  50. #define right(a,b) (a+b)/2+1,b
  51. #define mid(a,b) (a+b)/2
  52. void gl(char *str){register char c=0;register int i=0;while(c<33)c=get();while(c!='\n'){str[i]=c;c=get();i=i+1;}str[i]='\0';}
  53. void gfi(ft &x) {register ft c = get(); x = 0; ft sn=1;for(;(c<48 || c>57);c = get()) if(c=='-') sn=-1;for(;c>47 && c<58;c = get()) {x = (x<<1) + (x<<3) + c - 48;}x*=sn;}
  54. //int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
  55. //int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
  56. //int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
  57. //int dx[]={2,1,-1,-2,-1,1};int dy[]={0,1,1,0,-1,-1}; //Hexagonal Direction
  58.  
  59. #define N 5010
  60.  
  61. vi adj[N],cost[N];
  62. ll residual[N][N],duplicate[N][N],MAX=numeric_limits<ll>::max(),flow,maxFlow,n,m;
  63.  
  64. struct node {
  65. 	ll pre,cur,Flow;
  66. 	bool visit;
  67. }V[N];
  68.  
  69. typedef struct node nod;
  70.  
  71. struct cmp {
  72. 	bool operator() (nod x,nod y) {
  73. 		return x.Flow<y.Flow;
  74. 	}
  75. };
  76.  
  77. void findPath() {
  78. 	ref(i,1,n) {
  79. 		V[i].cur=i;
  80. 		V[i].pre=-1;
  81. 		V[i].visit=false;	
  82. 	}
  83. 	priority_queue<nod,vector<nod>,cmp> q;
  84. 	V[1].Flow=MAX;
  85. 	q.push(V[1]);
  86. 	while(!q.empty()) {
  87. 		ll pre,cur,Flow,curFlow;
  88. 		pre=q.top().cur;
  89. 		Flow=q.top().Flow;
  90. 		V[pre].visit=true;
  91. 		q.pop();
  92. 		if(pre==n) {
  93. 			flow=Flow;
  94. 			break;
  95. 		}
  96. 		rep(i,adj[pre].sz) {
  97. 			cur=adj[pre][i];	
  98. 			if(!V[cur].visit && residual[pre][cur]>0) {
  99. 				curFlow=min(Flow,residual[pre][cur]);
  100. 				V[cur].Flow=curFlow;
  101. 				V[cur].pre=pre;
  102. 				q.push(V[cur]);
  103. 			}
  104. 		}
  105. 	}
  106. 	ll cur,pre;
  107. 	cur=n;
  108. 	while(V[cur].pre!=-1) {
  109. 		pre=V[cur].pre;
  110. 		residual[pre][cur]-=flow;
  111. 		residual[cur][pre]+=flow;
  112. 		cur=pre;
  113. 	}
  114. }
  115.  
  116. int main() {
  117. 	gfi(n);gfi(m);
  118. 	rep(i,m) {
  119. 		ll u,v,c;
  120. 		gfi(u);gfi(v);gfi(c);
  121. 		if(u==v) continue;
  122. 		if(duplicate[u][v]) {
  123. 			residual[u][v]+=c;cost[u][duplicate[u][v]-1]+=c;
  124. 			residual[v][u]+=c;cost[v][duplicate[v][u]-1]+=c;
  125. 		} else {
  126. 			adj[u].pb(v);cost[u].pb(c);residual[u][v]+=c;duplicate[u][v]=adj[u].sz;
  127. 			adj[v].pb(u);cost[v].pb(c);residual[v][u]+=c;duplicate[v][u]=adj[v].sz;
  128. 		}	
  129. 	}
  130. 	maxFlow=0;
  131. 	findPath();
  132. 	while(flow) {
  133. 		maxFlow+=flow;
  134. 		flow=0;
  135. 		findPath();
  136. 	}
  137. 	cout << maxFlow << endl;
  138. 	return 0;
  139. }
  140.  
Time limit exceeded #stdin #stdout 5s 395584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Qp1iba
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

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!