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 a, b, c, u, f, back, mine;
  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 = {a,b,c,u,0,SZ(g[b]), SZ(g[a])};
  94. 		Edge e2 = {b,a,-c,0,0,SZ(g[a]), SZ(g[b])};
  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. 		set<pair<int,int> > Set;
  142. 		FOR(i,0,n)
  143. 			Set.insert(MP(d[i],i));
  144.  
  145. 		while(!Set.empty()) {
  146. 			PII r = *Set.begin();
  147. 			Set.erase(Set.begin());
  148. 			int v = r.Y;
  149. 			FOR(i,0,SZ(g[v])) if(g[v][i].f < g[v][i].u) {
  150. 				int to = g[v][i].b;
  151. 				if( d[to] > d[v] + g[v][i].c + phi[v] - phi[to] ) {
  152. 					Set.erase (make_pair (d[to], to));
  153.  
  154. 					d[to] = d[v] + g[v][i].c + phi[v] - phi[to];
  155. 					from[to] = v;
  156. 					from_edge[to] = i;
  157.  
  158. 					Set.insert (make_pair (d[to], to));
  159. 				}
  160. 			}
  161. 		}
  162. 	}
  163.  
  164. 	pair<FLOW,COST> minCostMaxFlow() {
  165. 		FLOW flow = 0;
  166. 		COST cost = 0;
  167. 		while(true) {
  168. 			//levit();
  169. 			dijkstra();
  170. 			for (int i = 0; i < n; i++)
  171. 				phi[i] += d[i];
  172. 			if(d[t]==INF)
  173. 				break;
  174. 			int it = t;
  175. 			FLOW addflow = FLOW_INF;
  176. 			while(it!=s) {
  177. 				addflow = min(addflow, g[from[it]][from_edge[it]].u - g[from[it]][from_edge[it]].f);
  178. 				it = from[it];
  179. 			}
  180. 			it = t;
  181. 			while(it!=s) {
  182. 				g[from[it]][from_edge[it]].f += addflow;
  183. 				g[it][g[from[it]][from_edge[it]].back].f -= addflow;
  184. 				cost += g[from[it]][from_edge[it]].c * addflow;
  185.  
  186. 				it = from[it];
  187. 			}
  188. 			flow += addflow;
  189. 		}
  190. 		return MP(flow, cost);
  191. 	}
  192. };
  193.  
  194. int main() {
  195. 	int n, c1, c2;
  196. 	int test;
  197. 	scanf("%d",&test);
  198. 	while(test--) {
  199. 		scanf("%d",&n);
  200. 		VI cnt(n,0);
  201. 		FOR(i,0,n) {
  202. 			int tt;
  203. 			scanf("%d",&tt);
  204. 			tt--;
  205. 			cnt[tt]++;
  206. 		}
  207. 		c1 = n;
  208. 		c2 = c1+1;
  209. 		MCMF t(c1,c2,n+2);
  210. 		FOR(i,0,n) {
  211. 			t.addEdge(c1,i,0,cnt[i]);
  212. 			t.addEdge(i,c2,0,1);
  213. 		}
  214. 		int e;
  215. 		scanf("%d",&e);
  216. 		FOR(i,0,e) {
  217. 			int a, b;
  218. 			scanf("%d%d",&a,&b);
  219. 			a--;b--;
  220. 			t.addEdge(a,b,1,1000);
  221. 			t.addEdge(b,a,1,1000);
  222. 		}
  223. 		pair<FLOW,COST> res = t.minCostMaxFlow();
  224. 		printf("%d\n",res.Y);
  225. 	}
  226. 	return 0;
  227. }
  228.  
Success #stdin #stdout 0s 3348KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/h1p9o4
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!