fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define REP(i,a,b) for (int i(a); i < (b); ++i)
  4. #define PER(i,a,b) for(int i((a)-1); i >= (b); --i)
  5. template<class T,class U>
  6. bool cmax(T & a, const U & b) {return a < b ? a = b, 1 : 0;}
  7. template<class T,class U>
  8. bool cmin(T & a, const U & b) {return b < a ? a = b, 1 : 0;}
  9. typedef long long ll;
  10. typedef pair<int,int> pii;
  11. typedef pair<ll,ll> pll;
  12. #define F first
  13. #define S second
  14. typedef vector<int> vi;
  15. typedef vector<ll> vll;
  16. #define SZ(a) ((int)(a).size())
  17. #define ALL(a) begin(a), end(a)
  18. #define PB push_back
  19. #define EB emplace_back
  20. typedef pair<long long, long long> pll;
  21. struct CostFlow {
  22. 	static const int MXN = 205;
  23. 	static const long long INF = 102938475610293847LL;
  24. 	struct Edge {
  25. 		int v, r;
  26. 		long long f, c;
  27. 	};
  28. 	int n, s, t, prv[MXN], prvL[MXN], inq[MXN];
  29. 	long long dis[MXN], fl, cost;
  30. 	vector<Edge> E[MXN];
  31. 	void init(int _n, int _s, int _t) {
  32. 		n = _n; s = _s; t = _t;
  33. 		for (int i=0; i<n; i++) E[i].clear();
  34. 		fl = cost = 0;
  35. 	}
  36. 	void add_edge(int u, int v, long long f, long long c) {
  37. 		E[u].PB({v, SZ(E[v])  , f,  c});
  38. 		E[v].PB({u, SZ(E[u])-1, 0, -c});
  39. 	}
  40. 	pll flow() {
  41.         while (true) {
  42.             for (int i=0; i<n; i++) {
  43.                 dis[i] = INF;
  44.                 inq[i] = 0;
  45.             }
  46.             dis[s] = 0;
  47. 			queue<int> que;
  48. 			que.push(s);
  49. 			while (!que.empty()) {
  50. 				int u = que.front(); que.pop();
  51. 				inq[u] = 0;
  52. 				for (int i=0; i<SZ(E[u]); i++) {
  53. 					int v = E[u][i].v;
  54. 					long long w = E[u][i].c;
  55. 					if (E[u][i].f > 0 && dis[v] > dis[u] + w) {
  56. 						prv[v] = u; prvL[v] = i;
  57. 						dis[v] = dis[u] + w;
  58. 						if (!inq[v]) {
  59. 							inq[v] = 1;
  60. 							que.push(v);
  61. 						}
  62. 					}
  63. 				}
  64. 			}
  65. 			if (dis[t] == INF) break;
  66. 			long long tf = INF;
  67. 			for (int v=t, u, l; v!=s; v=u) {
  68. 				u=prv[v]; l=prvL[v];
  69. 				tf = min(tf, E[u][l].f);
  70. 			}
  71. 			for (int v=t, u, l; v!=s; v=u) {
  72. 				u=prv[v]; l=prvL[v];
  73. 				E[u][l].f -= tf;
  74. 				E[v][E[u][l].r].f += tf;
  75. 			}
  76. 			cost += tf * dis[t];
  77. 			fl += tf;
  78. 		}
  79. 		return {fl, cost};
  80. 	}
  81. }flow;
  82. int mx[205], my[205];
  83. void getmc(int n,int m)
  84. {
  85.     fill_n(mx,n,-1);
  86.     fill_n(my,m,-1);
  87.     for (int i = 0; i < n; ++i)
  88.         for (const auto &  e : flow.E[i])
  89.             if (e.f == 0) {
  90.                 int j = e.v - n;
  91.                 if (0 <= j && j < m)
  92.                     mx[i] = j, my[j] = i;
  93.             }
  94. }
  95. class ShoppingSpree {
  96.     public:
  97.     int maxValue(int k, vector<int> a, vector<int> b, vector<int> x, vector<int> y) {
  98.         int n = a.size(), m = b.size(), d = x.size();
  99.         int s0 = n + m, s1 = n + m + 1, t = n + m + 2;
  100.         flow.init(n+m+3,s0,t);
  101.         for (int i = 0; i < n; ++i)
  102.             flow.add_edge(s1,i,1,0);
  103.         for (int i = 0; i < d; ++i)
  104.             flow.add_edge(x[i],n+y[i],1,-(a[x[i]]+b[y[i]]));
  105.         for (int i = 0; i < m; ++i)
  106.             flow.add_edge(n+i,t,1,0);
  107.         int ret = 0;
  108.         for (int j = 1; j <= k; ++j) {
  109.             flow.add_edge(s0,s1,1,0);
  110.             ll fl,co;
  111.             tie(fl,co) = flow.flow();
  112.             getmc(n,m);
  113.             vector<pii> ve;
  114.             for (int i = 0; i < d; ++i) {
  115.                 if (mx[x[i]] == -1 && my[y[i]] == -1)
  116.                     continue;
  117.                 if (mx[x[i]] != -1 && my[y[i]] != -1)
  118.                     continue;
  119.                 if (mx[x[i]] != -1) {
  120.                     ve.EB(b[y[i]], n+y[i]);
  121.                 }
  122.                 if (my[y[i]] != -1) {
  123.                     ve.EB(a[x[i]], x[i]);
  124.                 }
  125.             }
  126.             sort(ALL(ve),greater<pii>());
  127.             int su = -co;
  128.             for (int i = 0; i < k - j && i < ve.size(); ++i)
  129.                 su += ve[i].F;
  130.             //cerr << "su "<< su << endl;
  131.             ret = max(ret,su);
  132.         }
  133.         return ret;
  134.     }
  135. };
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout 
Standard output is empty
https://ideone.com/9moLb7
language:
C++14 (gcc 8.3)
created:
4 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!