题目链接  ：http://poj.org/problem?id=3436

题目很难理解，读题的时候读蒙了，看了好多解释才理解，简单点就是有很多机器来生产电脑，这些机器  可以通过利用一些零件生成或者销毁一些零件，也可能通过一些零件直接生成一台电脑。

利用的零件  给出的输入形式为  0代表这台机器工作的时候不需要这种零件，1代表必须要这种零件，2代表可有可无

工作产生的结果是输出形式为  1代表生成了这种零件，0代表没有生成这种零件

所以建图的时候  需要一个超级源点，一个超级汇点，由于在点上有权值，所以需要拆点

超级源点连接的是  输入形式中没有1的 容量为INF

超级汇点连接的是  输出形式中没有0的 容量为INF

某个点的输出如果是其他某些点的输入，也连起来，容量为INF

剩下的就是普通的最大流了

最后还有输出路径

输出的是那些   机器的输出恰好是机器的输入的那些边

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
const int maxn = 1e6+5;
struct node {
    int to;
    int cap;
    int rev;
    int flow;
    node(){}
    node(int a,int b,int c,int d):to(a),cap(b),flow(c),rev(d){}
};
struct Edge {
    int x;
    int y;
    int c;
};
vector<node> v[maxn];
vector<Edge> vv;
int d[maxn],cur[maxn],n,m,p,s,t,cnt;
void addedge(int from,int to,int cap) {
    v[from].push_back(node(to,cap,cap,v[to].size()));
    v[to].push_back(node(from,0,0,v[from].size()-1));
}
int dfs(int u,int flow) {
    if(u==t || !flow) return flow;
    int ans = 0;
    for(int &i = cur[u];i<v[u].size();i++) {
        node &e = v[u][i];
        if(d[e.to]  == d[u] + 1 && e.cap > 0) {
            int temp = dfs(e.to,min(flow,e.cap));
            if(temp>0) {
                flow-=temp;
                e.cap-=temp;
                v[e.to][e.rev].cap+=temp;
                ans += temp;
                if(!flow) break;
            }
        }
    }
    if(!ans) d[u] = -1;
    return ans;
}

bool bfs() {
    for(int i=0;i<=t;i++) d[i] = -1;
    queue<int> q;
    q.push(s);
    d[s] = 0;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i=0;i<v[u].size();i++) {
            int to = v[u][i].to;
            if(d[to]==-1 && v[u][i].cap>0) {
                d[to] = d[u] + 1;
                q.push(to);
            }
        }
    }
    return (d[t] != -1);
}

int dinic() {
    int max_flow = 0,tt;
    while(bfs()) {
        for(int i=s;i<=t;i++) cur[i] = 0;
        while((tt = dfs(s,INF)) > 0) max_flow+=tt;
    }
    return max_flow;
}
int pos[105][105];
int main()
{
    while(scanf("%d%d",&p,&n) != EOF) {
        vv.clear();
        s = 0, t = 2*n + 1;
        for(int i=s;i<=t;i++)v[i].clear();
        for(int i=1;i<=n;i++) {
            for(int j=0;j<2*p+1;j++) {
                scanf("%d",&pos[i][j]);
            }
        }
        for(int i=1;i<=n;i++) {
            addedge(i,i+n,pos[i][0]);
            int flag1=1,flag2=1;
            for(int j=1;j<=p;j++) {
                if(pos[i][j]==1){
                    flag1=0;
                    break;
                }
            }
            if(flag1) addedge(s,i,INF);
            for(int j=p+1;j<=2*p;j++) {
                if(pos[i][j]==0){
                    flag2=0;
                    break;
                }
            }
            if(flag2) addedge(i+n,t,INF);
        }
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                if(i==j)continue;
                int flag=1;
                for(int k=1;k<=p;k++) {
                    if(pos[i][k+p] != pos[j][k] && pos[j][k] != 2) {
                        flag=0;
                        break;
                    }
                }
                if(flag) {
                    addedge(i+n,j,INF);
                }
            }
        }
        int ans = dinic();cnt=0;
        for(int i=n+1;i<=2*n;i++) {
            for(int j=0;j<v[i].size();j++) {
                if(v[i][j].to != i-n && v[i][j].to>=1 && v[i][j].to <= n && v[i][j].cap != v[i][j].flow) {
                    Edge temp;
                    cnt++;
                    temp.x = i-n;
                    temp.y = v[i][j].to;
                    temp.c = v[i][j].flow - v[i][j].cap;
                    vv.push_back(temp);
                }
            }
        }
        printf("%d %d\n",ans,cnt);
        if(cnt)
        for(int i=0;i<vv.size();i++) {
            printf("%d %d %d\n",vv[i].x,vv[i].y,vv[i].c);
        }
    }
    return 0;
}