fork 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. 	int *from, *from_edge, *d, *phi, *state, *q;
  75. 	bool *used;
  76.  
  77. public:
  78. 	MCMF(int _s, int _t, int _n) {
  79. 		s = _s;
  80. 		t = _t;
  81. 		n = _n;
  82. 		from = new int[n];
  83. 		from_edge = new int[n];
  84. 		d = new int[n];
  85. 		state = new int[n];
  86. 		q = new int[n];
  87. 		phi = new int[n];
  88. 		FOR(i,0,n)
  89. 			phi[i] = 0;
  90. 		used = new bool[n];
  91. 	}
  92. 	void addEdge(int a, int b, int c, int u) {
  93. 		Edge e1 = {b,c,u,0,SZ(g[b])};
  94. 		Edge e2 = {a,-c,0,0,SZ(g[a])};
  95. 		g[a].PB(e1);
  96. 		g[b].PB(e2);
  97. 	}
  98.  
  99. 	void levit() {
  100. 		int qh, qt;
  101. 		qh = 0, qt = 0;
  102.  
  103. 		FOR(i,0,n) state[i] = 2, d[i] = INF;
  104. 		memset(from,-1,sizeof(from));
  105.  
  106. 		state[s] = 1;
  107. 		q[qh++] = s;
  108. 		d[s] = 0;
  109. 		while(qh!=qt) {
  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. 					qt--;if(qt==-1) qt = n-1;q[qt] = to;
  122. 					state[to] = 1;
  123. 				}
  124. 				else {
  125. 					state[to] = 1;
  126. 					q[qh++] = to;
  127. 					qh %= n;
  128. 				}
  129. 			}
  130. 		}
  131. 	}
  132.  
  133. 	void dijkstra() {
  134. 		memset(used,true,sizeof(used));
  135. 		used[s] = false;
  136. 		FOR(i,0,n)
  137. 			d[i] = INF;
  138.  
  139. 		d[s] = 0;
  140.  
  141. 		while(true) {
  142. 			int v = -1;
  143. 			for(int i=0;i<n;i++) {
  144. 				if(!used[i] && (v==-1 || d[v] > d[i]))
  145. 					v = i;
  146. 			}
  147. 			if(v==-1)
  148. 				break;
  149. 			used[v] = true;
  150. 			FOR(i,0,SZ(g[v])) if(g[v][i].f < g[v][i].u) {
  151. 				int to = g[v][i].b;
  152. 				if( d[to] > d[v] + g[v][i].c + phi[v] - phi[to] ) {
  153. 					d[to] = d[v] + g[v][i].c + phi[v] - phi[to];
  154. 					from[to] = v;
  155. 					from_edge[to] = i;
  156. 					used[to] = false;
  157. 				}
  158. 			}
  159. 		}
  160. 	}
  161.  
  162. 	pair<FLOW,COST> minCostMaxFlow() {
  163. 		FLOW flow = 0;
  164. 		COST cost = 0;
  165. 		while(true) {
  166. 			//levit();
  167. 			dijkstra();
  168. 			for (int i = 0; i < n; i++)
  169. 				phi[i] += d[i];
  170. 			if(d[t]==INF)
  171. 				break;
  172. 			int it = t;
  173. 			FLOW addflow = FLOW_INF;
  174. 			while(it!=s) {
  175. 				addflow = min(addflow, g[from[it]][from_edge[it]].u - g[from[it]][from_edge[it]].f);
  176. 				it = from[it];
  177. 			}
  178. 			it = t;
  179. 			while(it!=s) {
  180. 				g[from[it]][from_edge[it]].f += addflow;
  181. 				g[it][g[from[it]][from_edge[it]].back].f -= addflow;
  182. 				cost += g[from[it]][from_edge[it]].c * addflow;
  183.  
  184. 				it = from[it];
  185. 			}
  186. 			flow += addflow;
  187. 		}
  188. 		return MP(flow, cost);
  189. 	}
  190. };
  191.  
  192. int main() {
  193. 	int n, c1, c2;
  194. 	int test;
  195. 	scanf("%d",&test);
  196. 	while(test--) {
  197. 		scanf("%d",&n);
  198. 		VI cnt(n,0);
  199. 		FOR(i,0,n) {
  200. 			int tt;
  201. 			scanf("%d",&tt);
  202. 			tt--;
  203. 			cnt[tt]++;
  204. 		}
  205. 		c1 = n;
  206. 		c2 = c1+1;
  207. 		MCMF t(c1,c2,n+2);
  208. 		FOR(i,0,n) {
  209. 			t.addEdge(c1,i,0,cnt[i]);
  210. 			t.addEdge(i,c2,0,1);
  211. 		}
  212. 		int e;
  213. 		scanf("%d",&e);
  214. 		FOR(i,0,e) {
  215. 			int a, b;
  216. 			scanf("%d%d",&a,&b);
  217. 			a--;b--;
  218. 			t.addEdge(a,b,1,1000);
  219. 			t.addEdge(b,a,1,1000);
  220. 		}
  221. 		pair<FLOW,COST> res = t.minCostMaxFlow();
  222. 		printf("%d\n",res.Y);
  223. 	}
  224. 	return 0;
  225. }
  226.  
Success #stdin #stdout 0s 3344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/i5l2hK
language:
C++ (gcc 8.3)
created:
10 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!