zkw费用流模版

/**************************************************************

    Problem: 3876

    User: wangck1998

    Language: C++

    Result: Accepted

    Time:176 ms

    Memory:1456 kb

****************************************************************/

#include <bits/stdc++.h>

using namespace std;

#ifdef debug

#define ep(...) fprintf(stderr, __VA_ARGS__)

#else

#define ep(...) assert(true)

#endif

const int MAXN = 303;

const int INF = 0x3f3f3f3f;

const int MAXV = MAXN + 3;

const int MAXE = (5003 + MAXN * 2) * 2;

struct Edge {

  Edge* next;

  int dest;

  int cap;

  int val;

};

Edge memory[MAXE];

Edge* curMemory = memory;

Edge* info[MAXV];

void insert(int u, int v, int c, int l) {

  curMemory->next = info[u];

  curMemory->dest = v;

  curMemory->cap = c;

  curMemory->val = l;

  info[u] = curMemory++;

  curMemory->next = info[v];

  curMemory->dest = u;

  curMemory->cap = 0;

  curMemory->val = -l;

  info[v] = curMemory++;

}

Edge* oppsiteEdge(const Edge* const x) {

  return memory + ((x - memory) ^ 1);

}

int n;

int S, T;

int d[MAXV];

bool vis[MAXV];

int slack[MAXV];

Edge* pre[MAXV];

int dfs(int u, int flow) {

  if (u == T) return flow;

  vis[u] = true;

  int rest = flow;

  for (Edge* &pt = pre[u]; pt; pt = pt->next) {

    int v = pt->dest;

    if (pt->cap) {

      if (d[u] + pt->val == d[v] && ! vis[v]) {

        int temp = dfs(v, min(rest, pt->cap));

        if (temp) {

          rest -= temp;

          pt->cap -= temp;

          oppsiteEdge(pt)->cap += temp;

          if (rest == 0) return flow;

        }

      }

      else slack[v] = min(slack[v], d[u] + pt->val - d[v]);

    }

  }

  return flow - rest;

}

int maxFlow() {

  fill(d, d + T + 1, INF);

  d[S] = 0;

  queue<int> que;

  que.push(S);

  do {

    int u = que.front();

    que.pop();

    for (Edge* pt = info[u]; pt; pt = pt->next)

      if (pt->cap) {

        int v = pt->dest;

        int temp = d[u] + pt->val;

        if (temp < d[v]) {

          d[v] = temp;

          que.push(v);

        }

      }

  }while (! que.empty());

  int ret = 0;

  while (1) {

    while (1) {

      fill(vis, vis + T + 1, false);

      fill(slack, slack + T + 1, INF);

      copy(info, info + T + 1, pre);

      int temp = dfs(S, INF);

      if (temp) ret += (d[T] - d[S]) * temp;

      else break;

    }

    int temp = INF;

    for (int i = 0; i <= T; i++)

      if (! vis[i]) temp = min(temp, slack[i]);

    if (temp == INF) break;

    for (int i = 0; i <= T; i++)

      if (vis[i]) d[i] -= temp;

  }

  return ret;

}

int main() {

    scanf("%d", &n);

    S = 0, T = n + 1;

    int ans = 0;

    static int degree[MAXN];

    for (int i = 1; i <= n; i ++) {

        int m;

        scanf("%d", &m);

        degree[i] -= m;

        for (int j = 0; j < m; j ++) {

            int v, c;

            scanf("%d%d", &v, &c);

            degree[v] ++;

            insert(i, v, INF, c);

            ans += c;

        }

    }

    for (int i = 1; i <= n; i ++) {

        if (degree[i] > 0) {

            insert(S, i, degree[i], 0);

        }

        else if (degree[i] < 0) {

            insert(i, T, - degree[i], 0);

        }

        insert(i, 1, INF, 0);

    }

    printf("%d\n", ans + maxFlow());

    return 0;

}