fork(4) download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <sstream>
  4. #include <fstream>
  5. #include <cstdio>
  6. #include <algorithm>
  7. #include <deque>
  8. #include <vector>
  9. #include <map>
  10. #include <cmath>
  11. #include <cstdlib>
  12. #include <set>
  13. #include <queue>
  14. #include <stack>
  15. #include <string>
  16. #include <cstring>
  17. #include <climits>
  18. #include <ctype.h>
  19. #include <utility>
  20. using namespace std;
  21.  
  22.  
  23. typedef long long ll;
  24.  
  25. const int N = 105,INF = 1e9;
  26. vector<int> adj[N],vec[N],rvec[N];
  27. vector<pair<int,int> > ed; 
  28. int n, m, k, g[N][N], vis[N], par[N], qu[N], vs,from1[N],fromn[N],level[N],iter[N];
  29. bool used[N];
  30.  
  31. struct edge {
  32.     int to,cap,rev;
  33. };
  34. vector<edge> road[N];
  35. void add_edge(int from,int to,int cap) {
  36.     road[from].push_back((edge){to,cap,road[to].size()});
  37.     road[to].push_back((edge){from,0,road[from].size()-1});
  38. }
  39. void bfs(int s) {
  40.     memset(level,-1,sizeof(level));
  41.     queue<int> que;
  42.     level[s]=0;
  43.     que.push(s);
  44.     while(!que.empty()) {
  45.         int v=que.front();que.pop();
  46.         for(int i=0;i<road[v].size();i++) {
  47.             edge &e=road[v][i];
  48.             if (e.cap>0&&level[e.to]<0) {
  49.                 level[e.to]=level[v]+1;
  50.                 que.push(e.to);
  51.             }
  52.         }
  53.     }
  54. }
  55. int dfs(int v,int t,int f) {
  56.     if (v==t) return f;
  57.     used[v]=1;
  58.     for (int &i=iter[v];i<road[v].size();i++) {
  59.         edge &e=road[v][i];
  60.         if (e.cap>0&&level[v]<level[e.to]) {
  61.             int d=dfs(e.to,t,min(f,e.cap));
  62.             if (d>0) {
  63.                 e.cap-=d;
  64.                 road[e.to][e.rev].cap+=d;
  65.                 return d;
  66.             }
  67.         }
  68.     }
  69.     return 0;
  70. }
  71. int max_flow(int s,int t) {
  72.     int flow=0;
  73.     for (;;) {
  74.         bfs(s);
  75.         if (level[t]<0) return flow;
  76.         memset(iter,0,sizeof(iter));
  77.         int f;
  78.         while((f=dfs(s,t,INF))>0) flow+=f;
  79.     }
  80. }
  81. void spfa(int source,int *dist,vector<int> e[N]) {
  82. 	queue<int> que;int in_que[N+1];
  83. 	memset(in_que,0,sizeof(in_que));
  84. 	fill(dist,dist+N+1,INF);
  85. 	que.push(source);dist[source]=0;
  86. 	while(!que.empty()) {
  87. 		int u=que.front();que.pop();
  88. 		in_que[u]=0;
  89. 		for (int i=0;i<e[u].size();i++) {
  90. 			int to=e[u][i];
  91. 			if (dist[u]+1<dist[to]) {
  92. 				dist[to]=dist[u]+1;
  93. 				if (!in_que[to]) {
  94. 					que.push(to);in_que[to]=1;
  95. 				}
  96. 			}
  97. 		}
  98. 	}
  99. }
  100. int main(int argc, char **argv) {
  101. //	freopen("a", "r", stdin);
  102. //	freopen("b", "w", stdout);
  103. 	while (scanf("%d%d%d", &n, &m, &k) && n) {
  104. 		ed.clear();
  105. 		for (int i = 0; i < n * 2; ++i) {
  106. 			adj[i].clear();vec[i].clear();rvec[i].clear();
  107. 			road[i].clear();
  108. 			from1[i]=fromn[i]=INF;
  109. 		}
  110. 		add_edge(0, n, 1e9);
  111. 		for (int i = 0; i < n; ++i)
  112. 			add_edge(i, i + n, 1);
  113. 		while (m--) {
  114. 			int u, v;
  115. 			scanf("%d%d", &u, &v);
  116. 			--u;
  117. 			--v;
  118. 			vec[u].push_back(v);
  119. 			rvec[v].push_back(u);
  120. 			ed.push_back(make_pair(u,v));
  121. 		}
  122. 		spfa(0,from1,vec);
  123. 		spfa(n-1,fromn,rvec);
  124. 		for (int i=0;i<ed.size();i++) {
  125. 			int u=ed[i].first,v=ed[i].second;
  126. 			if (from1[u]+fromn[v]+1<=k) add_edge(u + n, v, INF);
  127. 		}
  128. 		if (n == 1)
  129. 			printf("%d\n", m);
  130. 		else
  131. 			printf("%d\n", max_flow(0, n - 1));
  132. 	}
  133. 	return 0;
  134. }
Success #stdin #stdout 0s 3352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/F7sfh4
language:
C++ (gcc 8.3)
created:
9 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!