fork(2) download 
  1. // iostream is too mainstream
  2. #include <cstdio>
  3. // bitch please
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <cstdlib>
  7. #include <vector>
  8. #include <set>
  9. #include <map>
  10. #include <queue>
  11. #include <stack>
  12. #include <list>
  13. #include <cmath>
  14. #include <iomanip>
  15. #define dibs reserve
  16. #define OVER9000 1234567890
  17. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  18. #define tisic 47
  19. #define soclose 1e-8
  20. #define chocolate win
  21. // so much chocolate
  22. #define patkan 9
  23. #define ff first
  24. #define ss second
  25. #define abs(x) ((x < 0)?-(x):x)
  26. #define uint unsigned int
  27. #define dbl long double
  28. using namespace std;
  29. // mylittledoge
  30.  
  31. int main() {
  32. 	cin.sync_with_stdio(0);
  33. 	cin.tie(0);
  34. 	int T;
  35. 	cin >> T;
  36. 	for(int t =0; t < T; t++) {
  37. 		int N,st,G,S,M,K;
  38. 		cin >> N >> st >> G >> S >> K;
  39. 		vector< vector< pair<int,int> > > E(N*(S+1)+2);
  40. 		vector< vector<int> > rev(N*(S+1)+2);
  41. 		// (S+1)*N: source
  42. 		// (S+1)*N+1: sink
  43. 		// numbered time*N+vertex
  44.  
  45. 		// from source
  46. 		rev[(S+1)*N].push_back(E[st-1].size());
  47. 		rev[st-1].push_back(E[(S+1)*N].size());
  48. 		E[(S+1)*N].push_back(make_pair(st-1,G));
  49. 		E[st-1].push_back(make_pair((S+1)*N,0));
  50.  
  51. 		// to sink
  52. 		for(int i =0; i < K; i++) {
  53. 			int a;
  54. 			cin >> a;
  55. 			a--;
  56. 			rev[S*N+a].push_back(E[(S+1)*N+1].size());
  57. 			rev[(S+1)*N+1].push_back(E[S*N+a].size());
  58. 			E[S*N+a].push_back(make_pair((S+1)*N+1,1000));
  59. 			E[(S+1)*N+1].push_back(make_pair(S*N+a,0));}
  60.  
  61. 		// self-loops
  62. 		for(int i =0; i < S*N; i++) {
  63. 			rev[i].push_back(E[i+N].size());
  64. 			rev[i+N].push_back(E[i].size());
  65. 			E[i].push_back(make_pair(i+N,1000));
  66. 			E[i+N].push_back(make_pair(i,0));}		  
  67.  
  68. 		// roads
  69. 		cin >> M;
  70. 		for(int i =0; i < M; i++) {
  71. 			int u,v,p,tt;
  72. 			cin >> u >> v >> p >> tt;
  73. 			u--, v--;
  74. 			for(int j =0; j <= S-tt; j++) {
  75. 				rev[j*N+u].push_back(E[(j+tt)*N+v].size());
  76. 				rev[(j+tt)*N+v].push_back(E[j*N+u].size());
  77. 				E[j*N+u].push_back(make_pair((j+tt)*N+v,p));
  78. 				E[(j+tt)*N+v].push_back(make_pair(j*N+u,0));}
  79. 		}
  80.  
  81. 		int f =0;
  82. 		N =E.size();
  83. 		queue<int> q;
  84. 		while(true) {
  85. 			vector< pair<int,int> > ako(N,make_pair(-1,-1));
  86. 			vector<int> F(N,G+1);
  87. 			q.push(N-2);
  88. 			while(!q.empty()) {
  89. 				for(int i =0; i < E[q.front()].size(); i++) if(ako[E[q.front()][i].ff].ff == -1 && E[q.front()][i].ss > 0) {
  90. 					F[E[q.front()][i].ff] =min(F[q.front()],E[q.front()][i].ss);
  91. 					ako[E[q.front()][i].ff] =make_pair(q.front(),i);
  92. 					q.push(E[q.front()][i].ff);}
  93. 				q.pop();}
  94. //			cout << F[N-1] << ".\n";
  95. 			if(F[N-1] == G+1) break;
  96.  
  97. 			f +=F[N-1];
  98. 			int akt =N-1;
  99. 			while(akt != N-2) {
  100. //				cout << akt << endl;
  101. 				int u =akt, v =ako[akt].ff, y =ako[akt].ss;
  102. //				cout << u << " " << v << "\n";
  103. 				int x =rev[v][y];
  104. 				E[u][x].ss +=F[N-1];
  105. 				E[v][y].ss -=F[N-1];
  106. 				akt =v;}
  107. 			}
  108.  
  109. 		cout << f << "\n";}
  110. 	return 0;}
  111.  
  112. // look at my code
  113. // my code is amazing
Success #stdin #stdout 0s 3440KB
comments (?)
stdin 
2
4
3 8 5
2
2
4
5
1 2 1 3
3 2 1 4
3 1 2 1
1 4 1 3
3 4 1 3
4
3 10 5
2
2
4
5
1 2 1 3
3 2 1 4
3 1 2 1
1 4 1 3
3 4 1 3
stdout 
8
9
https://ideone.com/JQOMyq
CT S02E08 A
language:
C++14 (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!