学步园

为什么要拆点：

2 4

10 0 0 0 1

10 0 0 0 0

10 0 1 1 1

10 0 1 1 1

拆点10， 不拆点20

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define maxn 106
#define inf 1000000000

int min(int a, int b)
{
    return a < b ? a : b;
}

struct E
{
    int v, next, c;
}edge[maxn * maxn << 1];

int head[maxn], tot;
int n, m;

void add(int s, int t, int c)
{
    edge[tot].v = t;
    edge[tot].c = c;
    edge[tot].next = head[s];
    head[s] = tot++;
    edge[tot].v = s;
    edge[tot].c = 0;
    edge[tot].next = head[t];
    head[t] = tot++;
}

void init()
{
    tot = 0;
    memset(head, -1, sizeof(head));
}

int gap[maxn], dis[maxn], cur[maxn], pre[maxn];
int sap(int s, int t, int vs)
{
    memset(gap, 0, sizeof(gap));
    memset(dis, 0, sizeof(dis));
    memcpy(cur, head, sizeof(head));
    gap[0] = vs;
    int i, v, u = pre[s] = s, maxf = 0, aug = inf;
    while(dis[s] < vs)
    {
loop:    for(i = head[u]; i != -1; i = edge[i].next)
         {
             v = edge[i].v;
             if(edge[i].c > 0 && dis[u] == dis[v] + 1)
             {
                 aug = min(aug, edge[i].c);
                 pre[v] = u;
                 cur[u] = i;
                 u = v;
                 if(u == t)
                 {
                     for(u = pre[u]; v != s; v = u, u = pre[u])
                     {
                         edge[cur[u]].c -= aug;
                         edge[cur[u]^1].c += aug;
                     }
                     maxf += aug;
                     aug = inf;
                 }
                 goto loop;
             }
         }
         int min_d = vs;
         for(i = head[u]; i != -1; i = edge[i].next)
         {
             v = edge[i].v;
             if(edge[i].c > 0 && dis[v] < min_d)
                 min_d = dis[v], cur[u] = i;
         }
         if(!(--gap[dis[u]])) break;
         ++gap[dis[u] = min_d + 1];
         u = pre[u];
    }
    return maxf;
}

struct node
{
    int a, b, c;
    node(){};
    node(int aa, int bb, int cc): a(aa), b(bb), c(cc){}
}ans[maxn];

int q[maxn], s[maxn][13], d[maxn][13];
int main()
{
    int i, j, k;
    while( ~scanf("%d%d", &m, &n))
    {
        int S = 0, T = n*2+1;    
        init();
        for(i = 1; i <= n; i++)
        {
            scanf("%d", &q[i]);
            add(i, i+n, q[i]);
            for(j = 1; j <= m; j++)
                scanf("%d", &s[i][j]);
            for(j = 1; j <= m; j++)
                scanf("%d", &d[i][j]);
        }
        for(i = 1; i <= n; i++)
        {
            int cnt = 0;
            for(j = 1; j <= m ; j++)
                if(s[i][j] == 0 || s[i][j] == 2) cnt++;
            if(cnt == m)
                add(S, i, inf);
            cnt = 0;
            for(j = 1; j <= m; j++)
                if(d[i][j] == 1) cnt++;
            if(cnt == m)
                add(i+n, T, inf);
        }
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
                if(i != j)
                {
                    int cnt = 0;
                    for(k = 1; k <= m; k++)
                        if(d[i][k] == s[j][k] || s[j][k] == 2)
                            cnt++;
                    if(cnt == m)
                        add(i+n, j, inf);
                }
        printf("%d", sap(S, T, T+1));
        int num = 0;
        for(i = n+1; i <= 2*n; i++)
        {
            for(j = head[i]; j != -1; j = edge[j].next)
            {
                int v = edge[j].v;
                if(v >= n+1 || v == S || v == T) continue;
                if(edge[j^1].c > 0 && i-n != v)
                    ans[num++] = node(i-n, v, edge[j^1].c);
            }
        }
        printf(" %d\n", num);
        for(i = 0; i < num; i++)
            printf("%d %d %d\n", ans[i].a, ans[i].b, ans[i].c);
    }
    return 0;
}