poj 3436

网络流，拆点建图，跑EK。
拆点建图这里有点麻烦，解决了就行，属于简单题。

#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#define INF 0x3f3f3f3f
#define MAX 200

using namespace std;

int p, n;
int data[MAX][MAX];
int in[MAX][MAX];
int out[MAX][MAX];
int gra[MAX][MAX]; //拆点后的图
int backup[MAX][MAX];
bool visit[MAX];
int pre[MAX];
int S, E;
stack<int> Q;
int A[MAX][MAX];

bool E_K() {
  memcpy(backup, gra, sizeof(gra));
  memset(visit, 0, sizeof(visit));
  while (!Q.empty()) {
    Q.pop();
  }
  visit[S] = true;
  Q.push(S);
  pre[S] = -1;
  while (!Q.empty()) {
    int front = Q.top();
    Q.pop();

    for (size_t i = 1; i <= 2 * n + 1; i++) {
      if (!visit[i] && gra[front][i] > 0) {
        Q.push(i);
        pre[i] = front;
        visit[i] = true;
      }
    }
  }

  return (visit[E] == true);
}

int Match(int *a, int *b) {
  int flag = 1;

  for (size_t i = 1; i <= p; i++) {
    if (a[i] == b[i])
      continue;
    if (a[i] == 2)
      continue;
    if (b[i] == 2)
      continue;

    flag = 0;
    break;
  }

  return flag;
}

int main() {
  while (~scanf("%d%d", &p, &n)) {
    memset(gra, 0, sizeof(gra));
    memset(pre, 0, sizeof(-1));
    S = 0;
    E = 2 * n + 1;

    for (size_t i = 1; i <= n; i++) {
      for (size_t j = 0; j < 2 * p + 1; j++) {
        scanf("%d", &data[i][j]);

        if (j < p + 1)
          in[i][j] = data[i][j];
        else
          out[i][j - p] = data[i][j];
      }
    }

    for (size_t i = 1; i <= n; i++) {
      gra[i * 2 - 1][i * 2] = data[i][0];
    }

    /****************建图***************/

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

      bool F_s = true;

      for (size_t j = 1; j <= p; j++) {

        if (in[i][j] == 1) {
          F_s = false;
          break;
        }
      }
      if (F_s)
        gra[S][2 * i - 1] = INF;

      bool F_e = true;

      for (size_t j = 1; j <= p; j++) {
        if (out[i][j] == 0) {
          F_e = false;
          break;
        }
      }
      if (F_e)
        gra[2 * i][E] = INF;
    }

    for (size_t i = 1; i <= n; i++) {
      for (size_t j = 1; j <= n; j++) {
        if (Match(out[i], in[j]) && i != j)
          gra[2 * i][2 * j - 1] = INF;
      }
    }

    /**************建图结束******************/
    int max_flow = 0;
    int t = 0;
    while (E_K()) {

      int path_flow = INF;
      for (int v = E; v != S; v = pre[v]) {
        int u = pre[v];
        if (path_flow > gra[u][v]) {
          path_flow = gra[u][v];
        }
      }

      for (int v = E; v != S; v = pre[v]) {
        int u = pre[v];
        gra[u][v] -= path_flow;
        gra[v][u] += path_flow;
      }
      max_flow += path_flow;
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
          if (i != j && gra[2 * i][2 * j - 1] < backup[2 * i][2 * j - 1]) {
            A[t][0] = path_flow;
            A[t][1] = i;
            A[t++][2] = j;
          }
        }
      }
    }
    printf("%d %d\n", max_flow, t);
    for (size_t i = 0; i < t; i++) {
      printf("%d %d %d\n", A[i][1], A[i][2], A[i][0]);
    }
  }

  return 0;
}