fork(13) download
copy 
  1. // Adjacency list implementation of FIFO push relabel maximum flow
  2. // with the gap relabeling heuristic.  This implementation is
  3. // significantly faster than straight Ford-Fulkerson.  It solves
  4. // random problems with 10000 vertices and 1000000 edges in a few
  5. // seconds, though it is possible to construct test cases that
  6. // achieve the worst-case.
  7. //
  8. // Running time:
  9. //     O(|V|^3)
  10. //
  11. // INPUT: 
  12. //     - graph, constructed using AddEdge()
  13. //     - source
  14. //     - sink
  15. //
  16. // OUTPUT:
  17. //     - maximum flow value
  18. //     - To obtain the actual flow values, look at all edges with
  19. //       capacity > 0 (zero capacity edges are residual edges).
  20.  
  21. #include <cmath>
  22. #include <vector>
  23. #include <iostream>
  24. #include <queue>
  25. #include <bits/stdc++.h>
  26. #define MAX 1000005
  27. #define ll long long
  28. #define upperlimit 1000100
  29. #define INF 1e18
  30. #define eps 1e-8
  31. #define endl '\n'
  32. #define pcc pair<char,char>
  33. #define pii pair<int,int>
  34. #define pll pair<ll,ll>
  35. #define tr(container,it) for(typeof(container.begin()) it=container.begin();it!=container.end();it++)
  36. #define MOD 1000000007LL
  37. #define slld(t) scanf("%lld",&t)
  38. #define sd(t) scanf("%d",&t)
  39. #define pd(t) printf("%d\n",t)
  40. #define plld(t) printf("%lld\n",t)
  41. #define mp(a,b) make_pair(a,b)
  42. #define FF first
  43. #define SS second
  44. #define pb(x) push_back(x)
  45. #define vi vector<int>
  46. #define vll vector<ll>
  47. #define clr(a) memset(a,0,sizeof(a))
  48. #define debug(a) printf("check%d\n",a)
  49. #define csl ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  50. using namespace std;
  51. typedef long long LL;
  52.  
  53. struct Edge {
  54.   int from, to, cap, flow, index;
  55.   Edge(int from, int to, int cap, int flow, int index) :
  56.     from(from), to(to), cap(cap), flow(flow), index(index) {}
  57. };
  58.  
  59. struct PushRelabel {
  60.   int N;
  61.   vector<vector<Edge> > G;
  62.   vector<LL> excess;
  63.   vector<int> dist, active, count;
  64.   queue<int> Q;
  65.  
  66.   PushRelabel(int N) : N(N), G(N), excess(N), dist(N), active(N), count(2*N) {}
  67.  
  68.   void AddEdge(int from, int to, int cap) {
  69.     G[from].push_back(Edge(from, to, cap, 0, G[to].size()));
  70.     if (from == to) G[from].back().index++;
  71.     G[to].push_back(Edge(to, from, 0, 0, G[from].size() - 1));
  72.   }
  73.  
  74.   void Enqueue(int v) { 
  75.     if (!active[v] && excess[v] > 0) { active[v] = true; Q.push(v); } 
  76.   }
  77.  
  78.   void Push(Edge &e) {
  79.     int amt = int(min(excess[e.from], LL(e.cap - e.flow)));
  80.     if (dist[e.from] <= dist[e.to] || amt == 0) return;
  81.     e.flow += amt;
  82.     G[e.to][e.index].flow -= amt;
  83.     excess[e.to] += amt;    
  84.     excess[e.from] -= amt;
  85.     Enqueue(e.to);
  86.   }
  87.  
  88.   void Gap(int k) {
  89.     for (int v = 0; v < N; v++) {
  90.       if (dist[v] < k) continue;
  91.       count[dist[v]]--;
  92.       dist[v] = max(dist[v], N+1);
  93.       count[dist[v]]++;
  94.       Enqueue(v);
  95.     }
  96.   }
  97.  
  98.   void Relabel(int v) {
  99.     count[dist[v]]--;
  100.     dist[v] = 2*N;
  101.     for (int i = 0; i < G[v].size(); i++) 
  102.       if (G[v][i].cap - G[v][i].flow > 0)
  103. 	dist[v] = min(dist[v], dist[G[v][i].to] + 1);
  104.     count[dist[v]]++;
  105.     Enqueue(v);
  106.   }
  107.  
  108.   void Discharge(int v) {
  109.     for (int i = 0; excess[v] > 0 && i < G[v].size(); i++) Push(G[v][i]);
  110.     if (excess[v] > 0) {
  111.       if (count[dist[v]] == 1) 
  112. 	Gap(dist[v]); 
  113.       else
  114. 	Relabel(v);
  115.     }
  116.   }
  117.  
  118.   LL GetMaxFlow(int s, int t) {
  119.     count[0] = N-1;
  120.     count[N] = 1;
  121.     dist[s] = N;
  122.     active[s] = active[t] = true;
  123.     for (int i = 0; i < G[s].size(); i++) {
  124.       excess[s] += G[s][i].cap;
  125.       Push(G[s][i]);
  126.     }
  127.  
  128.     while (!Q.empty()) {
  129.       int v = Q.front();
  130.       Q.pop();
  131.       active[v] = false;
  132.       Discharge(v);
  133.     }
  134.  
  135.     LL totflow = 0;
  136.     for (int i = 0; i < G[s].size(); i++) totflow += G[s][i].flow;
  137.     return totflow;
  138.   }
  139. };
  140. vector<pii> khali;
  141. vector<vector<pii>> adj;
  142. int n;
  143. bool visited[200];
  144. pii p[200];
  145. vi mera[200];
  146. int level[200];
  147. int u[3005],v[3005],cap[3005];
  148. vi bc;
  149. int solve(vector<bool> active,vector<vector<pii>> adj)
  150. {
  151. 	vector<int> temp;
  152. 	for(int i=0;i<active.size();i++)
  153. 	{
  154. 		if(active[i])
  155. 		{
  156. 			temp.pb(i);
  157. 			//cout<<i<<" ";
  158. 		}
  159. 	}
  160. 	//cout<<endl;
  161. 	if(temp.size()==1)
  162. 		return temp[0];
  163. 	int x=temp.size();
  164. 	PushRelabel pr(n);
  165. 	for(int i=0;i<n;i++)
  166. 	{
  167. 		for(auto j:adj[i])
  168. 		{
  169. 			pr.AddEdge(i,j.FF,j.SS);
  170. 			//pr.AddEdge(j.FF,i,j.SS);
  171. 		}
  172. 	}
  173. 	int ans=pr.GetMaxFlow(temp[0],temp[1]);
  174. 	//cout<<temp[0]<<" cut "<<temp[1]<<" "<<ans<<endl;
  175. 	clr(visited);
  176. 	queue<int> q;
  177. 	q.push(temp[0]);
  178. 	visited[temp[0]]=true;
  179. 	while(!q.empty())
  180. 	{
  181. 		int now=q.front();
  182. 		q.pop();
  183. 		for(auto x:pr.G[now])
  184. 		{
  185. 			if(x.cap-x.flow>0)
  186. 			{
  187. 				if(!visited[x.to])
  188. 				{
  189. 					q.push(x.to);
  190. 					visited[x.to]=true;
  191. 				}
  192. 			}
  193. 		}
  194. 	}
  195. 	std::vector<vector<pii>> xd(adj);
  196. 	vector<bool> tt(active);
  197. 	for(int i=0;i<n;i++)
  198. 	{
  199. 		if(visited[i])
  200. 		{
  201. 			//adj[i].clear();
  202. 			active[i]=0;
  203. 		}
  204. 		else
  205. 		{
  206. 			//xd[i].clear();
  207. 			tt[i]=0;
  208. 		}
  209. 	}
  210. 	int one=solve(tt,xd);
  211. 	int two=solve(active,adj);
  212. 	p[one]=mp(two,ans);
  213. 	mera[two].pb(one);
  214. 	//cout<<"joda "<<one<<" "<<two<<" "<<ans<<endl;
  215. 	return two;
  216. }
  217. void DFS(int x,int l)
  218. {
  219. 	level[x]=l;
  220. 	for(auto i:mera[x])
  221. 		DFS(i,l+1);
  222. }
  223. int main()
  224. {
  225. 	int t;
  226. 	cin>>t;
  227. 	while(t--)
  228. 	{
  229. 		adj.clear();
  230. 		clr(p);
  231. 		for(int i=0;i<200;i++)
  232. 			mera[i].clear();
  233. 		clr(level);
  234. 		bc.clear();
  235. 		int m;
  236. 		cin>>n>>m;
  237. 		for(int i=0;i<n;i++)
  238. 		{
  239. 			adj.pb(khali);
  240. 		}
  241. 		for(int i=0;i<m;i++)
  242. 		{
  243. 			cin>>u[i]>>v[i]>>cap[i];
  244. 			u[i]--;
  245. 			v[i]--;
  246. 			adj[u[i]].pb(mp(v[i],cap[i]));
  247. 			adj[v[i]].pb(mp(u[i],cap[i]));
  248. 		}
  249. 		vector<bool> active;
  250. 		for(int i=0;i<n;i++)
  251. 			active.pb(true);
  252. 		int root=solve(active,adj);
  253. 		DFS(root,1);
  254. 		for(int i=0;i<n;i++)
  255. 		{
  256. 			for(int j=i+1;j<n;j++)
  257. 			{
  258. 				int one=i,two=j,now=MOD;
  259. 				while(level[one]>level[two])
  260. 				{
  261. 					now=min(now,p[one].SS);
  262. 					one=p[one].FF;
  263. 				}
  264. 				while(level[one]<level[two])
  265. 				{
  266. 					now=min(now,p[two].SS);
  267. 					two=p[two].FF;
  268. 				}
  269. 				while(one!=two)
  270. 				{
  271. 					now=min(now,p[one].SS);
  272. 					one=p[one].FF;
  273. 					now=min(now,p[two].SS);
  274. 					two=p[two].FF;
  275. 				}
  276. 				bc.pb(now);
  277. 			}
  278. 		}
  279. 		sort(bc.begin(), bc.end());
  280. 		int q;
  281. 		cin>>q;
  282. 		while(q--)
  283. 		{
  284. 			int x;
  285. 			cin>>x;
  286. 			int asd=upper_bound(bc.begin(), bc.end(),x)-bc.begin();
  287. 			cout<<asd<<endl;
  288. 		}
  289. 	}
  290. }
Success #stdin #stdout 0s 4296KB
comments (?)
stdin
copy 
1
5 0
1 0
stdout
copy 
10
https://ideone.com/52tq6R
language:
C++14 (gcc 8.3)
created:
6 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!