fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pb push_back
  6. #define mp make_pair
  7. #define REP(i, n) for (int i = 0; i < (int)(n); ++i)
  8. typedef long long LL;
  9. typedef pair<int, int> PII;
  10.  
  11. const int N = 1111;
  12. const int INF = 1e9;
  13.  
  14. struct Edge {
  15.     int to, rev, cap, cost, f = 0;
  16.     Edge(int to, int rev, int cap, int cost) : to(to), rev(rev), cap(cap), cost(cost) {}
  17. };
  18.  
  19. vector<Edge> g[N];
  20. int nodes, src, dest;
  21. int prio[N], curFlow[N], prevEdge[N], prevNode[N], pot[N] = {};
  22. bool used[N];
  23.  
  24. void addEdge(int from, int to, int cap, int cost) {
  25.     g[from].pb(Edge(to, (int)g[to].size(), cap, cost));
  26.     g[to].pb(Edge(from, (int)g[from].size() - 1, 0, -cost));
  27. }
  28.  
  29. PII minCostFlow(int maxFlow) {
  30.     int flow = 0;
  31.     int flowCost = 0;
  32.     REP(i, nodes) pot[i] = 0;
  33.     while (flow < maxFlow) {
  34.         REP(i, nodes) prio[i] = INF;
  35.         prio[src] = 0;
  36.         curFlow[src] = INF;
  37.         REP(i, nodes) used[i] = false;
  38.         while (true) {
  39.             int v = -1;
  40.             REP(i, nodes) if (!used[i] && (v == -1 || prio[v] > prio[i])) {
  41.                 v = i;
  42.             }
  43.             if (v == -1 || prio[v] == INF) break;
  44.             used[v] = true;
  45.             REP(i, g[v].size()) {
  46.                 Edge &e = g[v][i];
  47.                 if (e.f >= e.cap) continue;
  48.                 int newPrio = prio[v] + e.cost + pot[v] - pot[e.to];
  49.                 if (prio[e.to] > newPrio) {
  50.                     prio[e.to] = newPrio;
  51.                     prevNode[e.to] = v;
  52.                     prevEdge[e.to] = i;
  53.                     curFlow[e.to] = min(curFlow[v], e.cap - e.f);
  54.                 }
  55.             }
  56.         }
  57.         if (prio[dest] == INF) break;
  58.         REP(i, nodes) if (prio[i] < INF) {
  59.             pot[i] += prio[i];
  60.         }
  61.         int df = min(curFlow[dest], maxFlow - flow);
  62.         flow += df;
  63.         flowCost += df * pot[dest];
  64.         for (int v = dest; v != src; v = prevNode[v]) {
  65.             Edge &e = g[prevNode[v]][prevEdge[v]];
  66.             e.f += df;
  67.             g[v][e.rev].f -= df;
  68.         }
  69.     }
  70.     return mp(flow, flowCost);
  71. }
  72.  
  73. int d[101];
  74. int n, k, c, m, qqq;
  75. int from[500], to[500], w[500];
  76. int ko[100][15];
  77. int cur[15];
  78.  
  79. int solve(int x, int y) {
  80.     src = n + k;
  81.     dest = src + 1;
  82.     nodes = dest + 1;
  83.     REP(i, nodes) g[i].clear();
  84.     REP(i, k) cur[i] = 0;
  85.     for (int i = x; i <= y; ++i) REP(j, k) {
  86.         cur[j] += ko[i][j];
  87.     }
  88.     REP(i, m) addEdge(from[i], n + to[i], 1, w[i] * cur[to[i]]);
  89.     int nz = 0;
  90.     REP(i, k) if (cur[i] > 0) {
  91.         addEdge(n + i, dest, 1, 0);
  92.         ++nz;
  93.     }
  94.     REP(i, n) {
  95.         addEdge(src, i, 1, 0);
  96.     }
  97.     PII res = minCostFlow(nz);
  98.     if (res.first != nz) return INF;
  99.     return res.second + c;
  100. }
  101.  
  102. int main() {
  103.     scanf("%d%d%d%d", &n, &k, &c, &m);
  104.     REP(i, m) {
  105.         scanf("%d%d%d", from + i, to + i, w + i);
  106.         --from[i], --to[i];
  107.     }
  108.     scanf("%d", &qqq);
  109.     REP(i, qqq) REP(j, k) scanf("%d", ko[i] + j);
  110.     d[0] = 0;
  111.     for (int i = 1; i <= qqq; ++i) d[i] = INF;
  112.     REP(i, qqq) {
  113.         for (int j = i; j < qqq; ++j) {
  114.             d[j + 1] = min(d[j + 1], d[i] + solve(i, j));
  115.         }
  116.     }
  117.     printf("%d\n", d[qqq]);
  118.     return 0;
  119. }
  120.  
Success #stdin #stdout 0s 3516KB
comments (?)
stdin
copy 
2 2 6
4
1 1 2
1 2 1
2 1 4
2 2 2
2
1 1
1 10
stdout
copy 
25
https://ideone.com/b55GJK
language:
C++14 (gcc 8.3)
created:
9 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!