水题

看到oj下面好多人说拆点。但是，我没有拆点却也做出来了。
从网络流的角度都去想没有什么障碍。我们构造出源点s和汇点t
然后看有哪些机器可以和源点连，即input清一色为0或2 连(s,i)cap=Q[i]
看有哪些可以可以与汇点连，即output都为1 连(i,t) cap = Q[i]

然后再看那些机器可以对接，i,j可以对接，即对于j的input，i的output可以满足
注意的是，这里连的边cap=Q[i]

再跑一便最大流就可以了！！！！

代码如下：

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pii> pip;
const int inf = 2e9;
struct edge{
    int to, cap, rev, next;
}E[10000];
int head[55];
int cnt = 1;
void add(int from, int to, int cap,int rev) {
    E[cnt].to = to;E[cnt].next = head[from];
    E[cnt].cap = cap;
    E[cnt].rev = rev;head[from] = cnt++;
}
int P, N;
int Q[60];
int in[60][15];
int out[60][15];

bool check_ed(int id) {
    for (int i = 1;i <= P;++i)
        if (out[id][i] != 1)return false;
    return true;
}
bool check_st(int id) {
    for (int i = 1;i <= P;++i)
        if (in[id][i] == 1)return false;
    return true;
}
bool check_ij(int ma, int mb) {
    for (int i = 1;i <= P;++i) {
        if (in[mb][i] == 1 && out[ma][i] == 0)return false;
        if (in[mb][i] == 0 && out[ma][i] == 1)return false;
    }return true;
}

int d[55];
bool searchpath(int s,int t) {
    fill(d, d + 55, -1);
    queue<int> que;d[s] = 0;
    que.push(s);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int i = head[u];i;i = E[i].next) {
            edge& e = E[i];
            if (d[e.to] != -1 || e.cap <= 0)continue;
            d[e.to] = d[u] + 1;
            que.push(e.to);
        }
    }return d[t] != -1;
}
int matchpath(int u,int t,int f) {
    if(u == t)return f;
    for (int i = head[u];i;i = E[i].next) {
        edge& e = E[i];
        if (d[e.to] <= d[u] || e.cap <= 0)continue;
        int flow = matchpath(e.to, t, min(f, e.cap));
        if (flow > 0) {
            e.cap -= flow;
            E[e.rev].cap += flow;
            return flow;
        }
    }return false;
}
int dinic(int st,int ed) {
    int flow = 0;int f;
    while (searchpath(st, ed))
        while (f = matchpath(st, ed, inf))
            flow += f;
    return flow;
}


vector<pip> res;
bool vis[55];
void bfs(int s,int t) {
    res.clear();
    fill(vis, vis + 55, false);
    queue<int> que;
    que.push(s);vis[s] = true;
    while (!que.empty()) {
        int u = que.front();
        que.pop();vis[u] = false;
        for (int i = head[u];i;i = E[i].next) {
            edge& e = E[i];
            if (e.rev & 1)continue;
            if (E[e.rev].cap == 0)continue;
            if (!vis[e.to]) {
                que.push(e.to);
                vis[e.to] = true;
            }
            if (u != s && e.to != t)
                res.push_back(make_pair(E[e.rev].cap, make_pair(u, e.to)));
        }
    }
}

int main() {
    while (scanf("%d %d", &P, &N)!=EOF) {
        if (P == 0 && N == 0)break;
        fill(head, head + 55, 0);cnt = 1;
        for (int i = 1;i <= N;++i) {
            scanf("%d", &Q[i]);
            for (int j = 1;j <= P;++j)scanf("%d", &in[i][j]);
            for (int j = 1;j <= P;++j)scanf("%d", &out[i][j]);
        }int start = N + 1;int ed = start + 1;
        for (int i = 1;i <= N;++i) {
            if (check_st(i)) {
                add(start, i, Q[i], cnt + 1);
                add(i, start, 0, cnt - 1);
            }
            if (check_ed(i)) {
                add(i, ed, Q[i], cnt + 1);
                add(ed, i, 0, cnt - 1);
            }
            for (int j = 1;j <= N;++j) {
                if (j != i && check_ij(i, j)) {
                    add(i, j, Q[i], cnt + 1);
                    add(j, i, 0, cnt - 1);
                }
            }
        }printf("%d ", dinic(start, ed));
        bfs(start, ed);printf("%d", res.size());
        for (int i = 0;i < res.size();++i)
            printf("\n%d %d %d", res[i].second.first, res[i].second.second, res[i].first);
    }
}