最大流 EK dinic sap

9404803

　　pku3281 Dining
　　题目分析：有N头牛，F种食物，D种饮料，要求给每头牛分配一份食物和一种饮料，每种食物和每种饮料只能供一头牛享用，问最多能满足多少头牛的需要。
　　建图：建一超级源点标号为0，连上所有的食物，边权为1，建一超级汇点标号为2 * N + F + D + 1,连上所有的饮料，边权为1，在构造N个点和N头牛一一对应，保证每头牛只享用一种食物和一种饮料，边权为1，每头牛享用的食物和对应的构造点相连，边权为1，N头牛在和他喜欢的饮料相连，边权为1。
　　数据量小，用EK写了下：跑了170多ms


代码



#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INF 0xfffffff
#define NN 410
int S, T;
int c[NN][NN];
int pre[NN];
int bfs()
{
    int que[NN];
    int mark[NN];
    memset(mark, 0, sizeof(mark));
    que[0] = S;
    mark[S] = 1;
    int tail,head, u, i;
    tail = head = 0;
    while(head <= tail){
        u = que[head++];
        for (i = 0; i <= T; i++){
            if (!mark && c > 0){
                mark = 1;
                que[++tail] = i;
                pre = u;
                if (i == T){
                    return 1;
                }
            }
        }
    }
    return 0;
}
void EK()
{
    int minf, t;
    int maxFlow = 0;
    while(bfs()){
        minf = INF;
        t = T;
        while(t != S){
            if (c[pre[t]][t] < minf){
                minf = c[pre[t]][t];
            }
            t = pre[t];
        }
        maxFlow += minf;
        t = T;
        while(t != S){
            c[pre[t]][t] -= minf;
            c[t][pre[t]] += minf;
            t = pre[t];
        }
    }
    printf("%d\n", maxFlow);
}
int main()
{
    int i, j, a, b, d, f, N, F, D;
    scanf("%d%d%d", &N, &F, &D);
    S = 0;
    T = 2 * N + F + D + 1;
    memset(c, 0, sizeof(c));
    for (i = 1; i <= F; i++){
        c[0][2 * N + i] = 1;
    }
    for (i = 1; i <= D; i++){
        c[2 * N + F + i][T] = 1;
    }
    for (i = 1; i <= N; i++){
        scanf("%d%d", &f, &d);
        for (j = 1; j <= f; j++){
            scanf("%d", &a);
            c[2 * N + a][N + i] = 1;
        }
　　　　 c[N + i] = 1;
        for (j = 1; j <= d; j++){
            scanf("%d", &b);
            c[2 * N + F + b] = 1;
        }
    }
    EK();
    //system("pause");
    return 0;
}

　　昨天刚看dinic，熟悉一下代码，又写了一个dinic的，用的单路增广dfs：0ms


代码



#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INF 0xfffffff
#define MM 60500
#define NN 410
int S, T, idx;
typedef struct node{
       int v, wt;
       struct node *nxt;
}NODE;
NODE edg[MM];
NODE *link[NN];
int h[NN];
int que[NN];
int Min(int a, int b){
    return a < b ? a : b;
}
void add(int u, int v, int x, int y){
     edg[idx].v = v;
     edg[idx].wt = x;
     edg[idx].nxt = link;
     link = edg + idx;
     idx++;
     edg[idx].v = u;
     edg[idx].wt = y;
     edg[idx].nxt = link[v];
     link[v] = edg + idx;
     idx++;
}
int bfs()
{
    int u, v, w, tail, head;
    memset(h, -1, sizeof(h));
    que[0] = S;
    h[S] = 0;
    tail = head = 0;
    while (head <= tail){
          u = que[head++];
          for (NODE *p = link; p; p = p->nxt){
              v = p->v;
              w = p->wt;
              if (h[v] == -1 && w > 0){
                 h[v] = h + 1;
                 que[++tail] = v;
              }
          }
    }
    return h[T] != -1;
}
int dfs(int u, int flow){
    if (u == T){
       return flow;
    }
    int tmpf = 0;
    int v, w, f;
    for (NODE *p = link; p; p = p->nxt){
        v = p->v;
        w = p->wt;
        if (h[v] == h + 1 && w && tmpf < flow &&(f = dfs(v, Min(w, flow - tmpf)))){
           p->wt -= f;
           int t = p - edg;
           if (t % 2 == 0){
              edg[t+1].wt += f;
           }else{
                edg[t-1].wt += f;
           }
           tmpf += f;
        }
    }
    if (tmpf == 0) h = -1;
    return tmpf;
}
void dinic()
{
     int ans = 0;
     while(bfs()){
        ans += dfs(S, INF);
     }
     printf("%d\n", ans);
}
int main()
{
    int i, j, a, b, d, f, N, F, D;
    scanf("%d%d%d", &N, &F, &D);
    S = 0;
    T = 2 * N + F + D + 1;
    idx = 0;
    for (i = S; i <= T; i++) link = 0;
    for (i = 1; i <= F; i++){
        add(0, 2 * N + i, 1, 0);
    }
    for (i = 1; i <= D; i++){
        add(2 * N + F + i, T, 1, 0);
    }
    for (i = 1; i <= N; i++){
        scanf("%d%d", &f, &d);
        for (j = 1; j <= f; j++){
            scanf("%d", &a);
            add(2 * N + a, N + i, 1, 0);
        }
        //刚开始把这个写到里面去了，用EK的时候邻接矩阵存的，没影响，
        //后来用了dinic，邻接表一存，多加了好多遍，WA了好多次
        add(N + i, i, 1, 0);
        for (j = 1; j <= d; j++){
            scanf("%d", &b);
            add(i, 2 * N + F + b, 1, 0);
        }
    }
    dinic();
    return 0;
}

　　正在学sap，就找了道题练了练，发现sap如果用递归形式写，真是太简单了。得感谢大牛：zkw
　　poj1459 Power Network


代码



#include<string.h>
#include<stdio.h>
#define INF 0xfffffff
#define MM 20500
#define NN 110
int S, T, idx;
typedef struct node{
        int v, wt;
        struct node *nxt;
}NODE;
NODE edg[MM];
NODE *link[NN];
int h[NN];
int que[NN];
int num[NN];
int Min(int a, int b){
     return a < b ? a : b;
}
/*加出边邻接表*/
void add(int u, int v, int x, int y){
     /*正向加边*/
     edg[idx].v = v;
     edg[idx].wt = x;
     edg[idx].nxt = link;
     link = edg + idx++;
     /*反向加边*/
     edg[idx].v = u;
     edg[idx].wt = y;
     edg[idx].nxt = link[v];
     link[v] = edg + idx++;
}
int dfs(int u, int flow){
    if (u == T){
       return flow;
    }
    int v, w, f;
    int tmp = T;
    int tf = flow;
    for (NODE *p = link; p; p = p->nxt){
        v = p->v;
        w = p->wt;
        if (h == h[v] + 1 && w){
            f = dfs(v, Min(w, tf));
           tf -= f;
            p->wt -= f;
           int t = p - edg;
           if (t % 2 == 0){
              edg[t+1].wt += f;
           }else{
                edg[t-1].wt += f;
           }
           if (!tf || h[S] == T + 1) return flow - tf;
        }
        // 这里要取的是《有剩余容量的边中》的距离标号的最小值
        if (h[v] < tmp && p->wt > 0) tmp = h[v];
    }
    if (!(--num[h])) h[S] = T + 1;
    else num[h = tmp + 1]++;
    return flow - tf;
}
void sap()
{
     int ans = 0;
     while (h[S] <  T + 1){
           ans += dfs(S, INF);
     }
     printf("%d\n", ans);
}
int main()
{
    int n, np, nc, m, a, b, d;
    while (scanf("%d%d%d%d", &n, &np, &nc, &m) != EOF){
        S = n;  //构造一个源点
        T = n + 1;//构造一个汇点
        idx = 0;
        memset(link, 0, sizeof(link));
        while (m--){
            scanf(" (%d,%d)%d", &a, &b, &d);
            if (a == b) continue;
            add(a, b, d, 0);
        }
        while (np--){
            scanf(" (%d)%d", &a, &d);
            add(S, a, d, 0);
        }
        while (nc--){
            scanf(" (%d)%d", &a, &d);
            add(a, T, d, 0);
        }
        memset(h, 0, sizeof(h));
        memset(num, 0, sizeof(num));
        sap();
    }
    return 0;
}