FLOW1 - Giao lưu

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>

const int N = 1111;
const int INF = int(1e9);

using namespace std;

int n, nProblem;

int contestant(int side, int id) {
  return n * side + id;
}

int problem(bool out, int id) {
  return n + n + nProblem * out + id;
}

struct edge {
  int u, v;
  int cap, flow;

  edge(int _u, int _v, int _c) {
    u = _u; v = _v; cap = _c;
    flow = 0;
  }
};

struct network {
  int n;
  int source, sink;
  int maxFlow;
  int T[N];
  vector<int> a[N];
  vector<edge> E;

  void addEdge(int u, int v, int c) {
    a[u].push_back(E.size()); //* forward
    a[v].push_back(E.size() + 1); //* reverse
    E.push_back(edge(u, v, c));
    E.push_back(edge(v, u, 0)); //* directed graph
  }

  bool findPath() {
    queue<int> Q;
    Q.push(source);
    for (int i = 1; i <= n; ++i)
      T[i] = 0;
    while (!Q.empty()) {
      int u = Q.front(); Q.pop();
      for (int id: a[u]) {
        int v = E[id].v;
        if (T[v] == 0 && E[id].cap > E[id].flow) {
          T[v] = id;
          if (v == sink) return 1;
          Q.push(v);
        }
      }
    }
    return 0;
  }

  void incFlow() {
    int delta = INF;
    for (int v = sink, u = T[v]; v != source; v = E[u].u, u = T[v])
      delta = min(delta, E[u].cap - E[u].flow);
    for (int v = sink, u = T[v]; v != source; v = E[u].u, u = T[v])
      E[u].flow += delta, E[u ^ 1].flow -= delta;
    maxFlow += delta;
  }

  void edmondsKarp() {
    while (findPath()) incFlow();
  }

  int getFlow(int u, int v) {
    for (int id: a[u])
    if (E[id].v == v)
     return E[id].flow;
    return 0;
  }
} G;

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
#ifdef _LAD_
  freopen("FLOW1.txt", "r", stdin);
#endif // _LAD_
  cin >> n >> nProblem;

  G.source = n + n + nProblem + nProblem + 1;
  G.sink = G.n = G.source + 1; //* number of vertexes equals sink

  string line;
  getline(cin, line);
  for (int side = 0; side <= 1; ++side) {
    for (int i = 1; i <= n; ++i) {
      getline(cin, line);
      istringstream input(line);
      int prob;
      while (input >> prob) {
        if (side == 0)
          G.addEdge(contestant(side, i), problem(0, prob), 1);
        else
          G.addEdge(problem(1, prob), contestant(side, i), 1);
      }
    }
  }

  for (int i = 1; i <= n; ++i)
    G.addEdge(G.source, contestant(0, i), 1);
  for (int i = 1; i <= n; ++i)
    G.addEdge(contestant(1, i), G.sink, 1);
  for (int i = 1; i <= nProblem; ++i)
    G.addEdge(problem(0, i), problem(1, i), 1);

  G.edmondsKarp();
  for (int i = 1; i <= nProblem; ++i) {
    if (G.getFlow(problem(0, i), problem(1, i))) {
      for (int id: G.a[problem(0, i)])
      if (G.E[id].v <= n && G.E[id].flow) {
        cout << G.E[id].v << ' ';
        break;
      }
      for (int id: G.a[problem(1, i)])
      if (n < G.E[id].v && G.E[id].v <= n + n && G.E[id].flow) {
        cout << G.E[id].v - n << endl;
        break;
      }
    } else {
      cout << 0 << ' ' << 0 << endl;
    }
  }
  return 0;
}

Download