fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int, int> pi;
  4. typedef long long lint;
  5.  
  6. const int MAXN = 222;
  7. struct maxflow{
  8. 	struct edg{int pos, cap, rev, idx;};
  9. 	vector<edg> gph[MAXN];
  10.  
  11. 	void clear(){
  12. 		for(int i=0; i<MAXN; i++){
  13. 			gph[i].clear();
  14. 		}
  15. 	}
  16.  
  17. 	void add_edge(int s, int e, int x){
  18. 		gph[s].push_back({e, x, (int)gph[e].size(), -1});
  19. 		gph[e].push_back({s, 0, (int)gph[s].size()-1, -1});
  20. 	}
  21.  
  22. 	void add_edge(int s, int e, int x, int idx){
  23. 		gph[s].push_back({e, x, (int)gph[e].size(), idx});
  24. 		gph[e].push_back({s, 0, (int)gph[s].size()-1, -1});
  25. 	}
  26.  
  27. 	int dis[MAXN], pnt[MAXN];
  28.  
  29. 	bool bfs(int src, int sink){
  30. 		memset(dis, 0, sizeof(dis));
  31. 		memset(pnt, 0, sizeof(pnt));
  32. 		queue<int> que;
  33. 		que.push(src);
  34. 		dis[src] = 1;
  35. 		while(!que.empty()){
  36. 			int x = que.front();
  37. 			que.pop();
  38. 			for(int i=0; i<gph[x].size(); i++){
  39. 				edg e = gph[x][i];
  40. 				if(e.cap > 0 && !dis[e.pos]){
  41. 					dis[e.pos] = dis[x] + 1;
  42. 					que.push(e.pos);
  43. 				}
  44. 			}
  45. 		}
  46. 		return dis[sink] > 0;
  47. 	}
  48.  
  49. 	int dfs(int x, int sink, int f){
  50. 		if(x == sink) return f;
  51. 		for(; pnt[x] < gph[x].size(); pnt[x]++){
  52. 			edg e = gph[x][pnt[x]];
  53. 			if(e.cap > 0 && dis[e.pos] == dis[x] + 1){
  54. 				int w = dfs(e.pos, sink, min(f, e.cap));
  55. 				if(w){
  56. 					gph[x][pnt[x]].cap -= w;
  57. 					gph[e.pos][e.rev].cap += w;
  58. 					return w;
  59. 				}
  60. 			}
  61. 		}
  62. 		return 0;
  63. 	}
  64.  
  65. 	lint match(int src, int sink){
  66. 		lint ret = 0;
  67. 		while(bfs(src, sink)){
  68. 			int r;
  69. 			while((r = dfs(src, sink, 2e9))) ret += r;
  70. 		}
  71. 		return ret;
  72. 	}
  73. }maxflow;
  74.  
  75. int n, m;
  76. int ret[20005];
  77.  
  78. int main(){
  79. 	freopen("cooling.in", "r", stdin);
  80. 	freopen("cooling.out", "w", stdout);
  81. 	cin >> n >> m;
  82. 	int flow = 0;
  83. 	for(int i=0; i<m; i++){
  84. 		int s, e, l, r;
  85. 		cin >> s >> e >> l >> r;
  86. 		ret[i] += r;
  87. 		maxflow.add_edge(s, e, r-l, i);
  88. 		maxflow.add_edge(0, e, l);
  89. 		maxflow.add_edge(s, n+1, l);
  90. 		flow += l;
  91. 	}
  92. 	if(maxflow.match(0, n+1) != flow){
  93. 		puts("NO");
  94. 		return 0;
  95. 	}
  96. 	for(int i=1; i<=n; i++){
  97. 		for(auto &j : maxflow.gph[i]){
  98. 			if(j.idx != -1){
  99. 				ret[j.idx] -= j.cap;
  100. 			}
  101. 		}
  102. 	}
  103. 	puts("YES");
  104. 	for(int i=0; i<m; i++) printf("%d\n", ret[i]);
  105. }
Success #stdin #stdout 0s 3552KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7INqrF
language:
C++14 (gcc 8.3)
created:
8 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!