fork(4) download
copy 
  1. //#pragma comment(linker,"/STACK:16777216") /*16Mb*/
  2. //#pragma comment(linker,"/STACK:33554432") /*32Mb*/
  3. #define _CRT_SECURE_NO_DEPRECATE
  4. #include<sstream>
  5. #include<iostream>
  6. #include<numeric>
  7. #include<sstream>
  8. #include<cstdio>
  9. #include<cstdlib>
  10. #include<cmath>
  11. #include<memory>
  12. #include<memory.h>
  13. #include<string>
  14. #include<vector>
  15. #include<cctype>
  16. #include<list>
  17. #include<queue>
  18. #include<deque>
  19. #include<stack>
  20. #include<map>
  21. #include<complex>
  22. #include<set>
  23. #include<algorithm>
  24.  
  25. using namespace std;
  26.  
  27. typedef unsigned long long      ui64;
  28. typedef long long               i64;
  29. typedef    vector<int>             VI;
  30. typedef	vector<bool>            VB;
  31. typedef	vector<VI>              VVI;
  32. typedef	vector<string>          VS;
  33. typedef	pair<int,int>           PII;
  34. typedef map<string,int>         MSI;
  35. typedef set<int>                SI;
  36. typedef set<string>             SS;
  37. typedef complex<double>         CD;
  38. typedef vector< CD >            VCD;
  39. typedef map<int,int>            MII;
  40. typedef	pair<double,double>     PDD;
  41.  
  42. #define PB                      push_back
  43. #define MP                      make_pair
  44. #define X                       first
  45. #define Y                       second
  46. #define FOR(i, a, b)            for(int i = (a); i < (b); ++i)
  47. #define RFOR(i, a, b)           for(int i = (a) - 1; i >= (b); --i)
  48. #define CLEAR(a, b)             memset(a, b, sizeof(a))
  49. #define SZ(a)                   int((a).size())
  50. #define ALL(a)                  (a).begin(), (a).end()
  51. #define RALL(a)                 (a).rbegin(), (a).rend()
  52.  
  53. #ifdef _DEBUG
  54. #define eprintf(...) fprintf (stderr, __VA_ARGS__)
  55. #else
  56. #define eprintf(...) assert (true)
  57. #endif
  58.  
  59. const double PI = acos(-1.0);
  60.  
  61. typedef int FLOW;
  62. typedef int COST;
  63. const COST INF = 1000000000;
  64. const FLOW FLOW_INF = 1000000000;
  65. const int MAXN = 10000;
  66. struct Edge {
  67. 	int b, c, u, f, back;
  68. };
  69.  
  70. class MCMF {
  71. private:
  72. 	int s, t, n;
  73. 	vector<Edge> g[MAXN];
  74. public:
  75. 	MCMF(int _s, int _t, int _n) {
  76. 		s = _s;
  77. 		t = _t;
  78. 		n = _n;
  79. 	}
  80. 	void addEdge(int a, int b, int c, int u) {
  81. 		Edge e1 = {b,c,u,0,SZ(g[b])};
  82. 		Edge e2 = {a,-c,0,0,SZ(g[a])};
  83. 		g[a].PB(e1);
  84. 		g[b].PB(e2);
  85. 	}
  86. 	pair<FLOW,COST> minCostMaxFlow() {
  87. 		FLOW flow = 0;
  88. 		COST cost = 0;
  89. 		int *state = new int[n];
  90. 		int *from = new int[n];
  91. 		int *from_edge = new int[n];
  92. 		int *d = new int[n];
  93. 		int *q = new int[n];
  94. 		int qh, qt;
  95. 		qh = 0, qt = 0;
  96. 		while(true) {
  97. 			//find path
  98. 			FOR(i,0,n) state[i] = 2, d[i] = INF;
  99. 			memset(from,-1,sizeof(from));
  100.  
  101. 			state[s] = 1;
  102. 			//deque<int> q;
  103. 			//q.push_back(s);
  104. 			q[qh++] = s;
  105. 			d[s] = 0;
  106. 			//while(!q.empty()) {
  107. 			while(qh!=qt) {
  108. 				//int v = q.front();
  109. 				//q.pop_front();
  110. 				int v = q[qt++];
  111. 				qt %= n;
  112. 				state[v] = 0;
  113. 				FOR(i,0,SZ(g[v])) if(g[v][i].f < g[v][i].u && d[g[v][i].b] > d[v] + g[v][i].c) {
  114. 					int to = g[v][i].b;
  115. 					d[to] = d[v] + g[v][i].c;
  116. 					from[to] = v;
  117. 					from_edge[to] = i;
  118. 					if(state[to]==1)
  119. 						continue;
  120. 					if(state[to]==0) {
  121. 						//q.push_front(to);
  122. 						qt--;if(qt==-1) qt = n-1;q[qt] = to;
  123.  
  124. 						state[to] = 1;
  125. 					}
  126. 					else {
  127. 						//never touched before
  128. 						state[to] = 1;
  129. 						//q.push_back(to);
  130. 						q[qh++] = to;
  131. 						qh %= n;
  132. 					}
  133. 				}
  134. 			}
  135. 			if(d[t]==INF)
  136. 				break;
  137. 			int it = t;
  138. 			FLOW addflow = FLOW_INF;
  139. 			while(it!=s) {
  140. 				addflow = min(addflow, g[from[it]][from_edge[it]].u - g[from[it]][from_edge[it]].f);
  141. 				it = from[it];
  142. 			}
  143. 			it = t;
  144. 			while(it!=s) {
  145. 				g[from[it]][from_edge[it]].f += addflow;
  146. 				g[it][g[from[it]][from_edge[it]].back].f -= addflow;
  147. 				cost += g[from[it]][from_edge[it]].c * addflow;
  148.  
  149. 				it = from[it];
  150. 			}
  151. 			flow += addflow;
  152. 		}
  153. 		return MP(flow, cost);
  154. 	}
  155. };
  156.  
  157. int main() {
  158. 	int n, c1, c2;
  159. 	int test;
  160. 	scanf("%d",&test);
  161. 	while(test--) {
  162. 		scanf("%d",&n);
  163. 		VI cnt(n,0);
  164. 		FOR(i,0,n) {
  165. 			int tt;
  166. 			scanf("%d",&tt);
  167. 			tt--;
  168. 			cnt[tt]++;
  169. 		}
  170. 		c1 = n;
  171. 		c2 = c1+1;
  172. 		MCMF t(c1,c2,n+2);
  173. 		FOR(i,0,n) {
  174. 			t.addEdge(c1,i,0,cnt[i]);
  175. 			t.addEdge(i,c2,0,1);
  176. 		}
  177. 		int e;
  178. 		scanf("%d",&e);
  179. 		FOR(i,0,e) {
  180. 			int a, b;
  181. 			scanf("%d%d",&a,&b);
  182. 			a--;b--;
  183. 			t.addEdge(a,b,1,1000);
  184. 			t.addEdge(b,a,1,1000);
  185. 		}
  186. 		pair<FLOW,COST> res = t.minCostMaxFlow();
  187. 		printf("%d\n",res.Y);
  188. 	}
  189. 	return 0;
  190. }
  191.  
Success #stdin #stdout 0s 3344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/S9BQ89
language:
C++ (gcc 8.3)
created:
11 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!