fork download 
  1. #include<stdio.h>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<string.h>
  5. #include<map>
  6. using namespace std;
  7. typedef pair<int, int> pii;
  8. using lld = long long int;
  9. #define INF 1000000009
  10. #define MAX_N 3009
  11. struct Edge {
  12. 	int s, t;
  13. 	int f;
  14. 	int c;
  15. 	int ri;
  16. 	Edge() {
  17. 		s = t = 0;
  18. 		f = c = ri = 0;
  19. 	}
  20. 	Edge(int s, int t, int c) :s(s), t(t), c(c) {
  21. 		f = 0; ri = 0;
  22. 	}
  23. };
  24. int adn;
  25. vector<Edge> dinic_v[MAX_N];
  26. void inil() {
  27. 	int i, j, k;
  28. 	for (i = 0; i < adn; i++) {
  29. 		dinic_v[i].clear();
  30. 	}
  31. }
  32. void add_edge(int si, int ei, int c, int cr = 0) {
  33. 	dinic_v[si].push_back(Edge(si, ei, c));
  34. 	dinic_v[ei].push_back(Edge(ei, si, cr));
  35. 	dinic_v[si].back().ri = ((int)dinic_v[ei].size()) - 1;
  36. 	dinic_v[ei].back().ri = ((int)dinic_v[si].size()) - 1;
  37. }
  38. int dinic_level[MAX_N];
  39. int dinic_mark[MAX_N];
  40. int dinic_que[MAX_N];
  41. int dinic_q, dinic_r;
  42. bool dinic_bfs(int si, int ei) {
  43. 	int i, j, k;
  44. 	for (i = 0; i < adn; i++) {
  45. 		dinic_mark[i] = 0;
  46. 		dinic_level[i] = -1;
  47. 	}
  48. 	dinic_q = dinic_r = 0;
  49. 	dinic_level[si] = 0;
  50. 	dinic_mark[si] = 1;
  51. 	dinic_que[dinic_r++] = si;
  52. 	while (dinic_q < dinic_r) {
  53. 		int qi = dinic_que[dinic_q++];
  54. 		for (i = 0; i < dinic_v[qi].size(); i++) {
  55. 			if (dinic_v[qi][i].c - dinic_v[qi][i].f > 0) {
  56. 				j = dinic_v[qi][i].t;
  57. 				if (dinic_level[j] == -1) {
  58. 					dinic_level[j] = dinic_level[qi] + 1;
  59. 					dinic_mark[j] = 1;
  60. 					dinic_que[dinic_r++] = j;
  61. 				}
  62. 			}
  63. 		}
  64. 	}
  65. 	return dinic_mark[ei];
  66. }
  67. int dinic_vsi[MAX_N];
  68. lld dinic_dfs(int si, int ei, int flow) {
  69. 	int i, j, k;
  70. 	if (si == ei)return flow;
  71. 	for (int &i = dinic_vsi[si]; i < dinic_v[si].size(); i++) {
  72. 		if (dinic_v[si][i].c - dinic_v[si][i].f > 0) {
  73. 			j = dinic_v[si][i].t;
  74. 			if (dinic_level[j] == dinic_level[si] + 1) {
  75. 				int ff = min(flow, dinic_v[si][i].c - dinic_v[si][i].f);
  76. 				int ret = dinic_dfs(j, ei, ff);
  77. 				if (ret > 0) {
  78. 					dinic_v[si][i].f += ret;
  79. 					dinic_v[dinic_v[si][i].t][dinic_v[si][i].ri].f -= ret;
  80. 					return ret;
  81. 				}
  82. 			}
  83. 		}
  84. 	}
  85. 	return -1;
  86. }
  87. lld network_flow(int si, int ei) {
  88.     lld flow = 0;
  89. 	while (dinic_bfs(si, ei)) {
  90. 		for (int i = 0; i < adn; i++)dinic_vsi[i] = 0;
  91. 		do {
  92.             int ret = dinic_dfs(si, ei, INF);
  93. 			if (ret < 0)break;
  94. 			flow += ret;
  95. 		} while (1);
  96. 	}
  97. 	return flow;
  98. }
  99. ////
  100. int n,m;
  101. // minimize r0+r1+c0+c1+c2 when A*x >= a
  102. // LP dual
  103. // maximize a[][]*y when At*y <= 1 <-- min cost max flow
  104. int main(){
  105.     int i,j,k;
  106.     scanf("%d %d",&n,&m);
  107.     adn=n+m+2;
  108.     inil();
  109.     for(i=0;i<n;i++){
  110.         add_edge(adn-2,i,INF);
  111.         for(j=0;j<m;j++){
  112.             scanf("%d",&k);
  113.             add_edge(i,j+n,k);
  114.         }
  115.     }
  116.     for(i=0;i<m;i++){
  117.         add_edge(i+n,adn-1,INF);
  118.     }
  119.     printf("%lld\n",network_flow(adn-2,adn-1));
  120. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin 
2 3
2 1 2
3 1 1
stdout 
10
https://ideone.com/EkqEZd
language:
C++14 (gcc 8.3)
created:
7 days 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!