学步园

PIGS

用EK就能做。

盗用大牛讲解：

题目大意：

有 M 个猪圈（M ≤ 1000），每个猪圈里初始时有若干头猪。

一开始所有猪圈都是关闭的。

依次来了 N 个顾客（N ≤ 100），每个顾客分别会打开指定的几个猪圈，从中买若干头猪。

每个顾客分别都有他能够买的数量的上限。

每个顾客走后，他打开的那些猪圈中的猪，都可以被任意地调换到其它开着的猪圈里，然后所有猪圈重新关上。

详解见：原创博客

这题关键：建一个超级源点，连上所有的商人，边权置为每个顾客能打开的猪圈里猪的总数，建一个超级汇点，每个顾客都连上这个汇点，权值为每个顾客的购买上限，如果猪圈i先被顾客p1打开，紧接着又被p2打开，加一条从p1到p2的边，边权为INF。

我EK写了两遍：

第一个：407ms

#include<queue>
#include<stdio.h>
using namespace std;

#define NN 104
#define INF 0x5fffffff
int M, N;
int c[NN][NN];
int mark[NN];
int pre[NN];
void CreateGraph()
{
int i, j, cnt, t, x[1004], flag[1004];
for (i = 0; i <= N + 1; i++){
for (j = 0; j <= N + 1; j++){
            c[i][j] = 0;
        }
    }
for (i = 1; i <= M; i++){
        scanf("%d", &x[i]);
        flag[i] = -1; // 标记第i个猪圈刚被哪个商人打开过
    }

for (i = 1; i <= N; i++){
        scanf("%d", &cnt);
for (j = 1; j <= cnt; j++){
            scanf("%d", &t);
if (flag[t] != -1){
                c[flag[t]][i] = INF;
            }else{
                c[0][i] += x[t];
            }
            flag[t] = i;
        }
        scanf("%d", &t);
        c[i][N + 1] = t;
    }
}

int Bfs()
{
int que[NN];
     memset(mark, 0, sizeof(mark));
     mark[0] = 1;
     que[0] = 0;
int cur, i;
int flow = INF;
int j, num = 1;
for (j = 0; j < num; j++) {
         cur = que[j];
for (i = 0; i <= N + 1; i++){
if (c[cur][i] > 0 && !mark[i]){
                mark[i] = 1;
if (c[cur][i] < flow){
                   flow = c[cur][i];
                }
                pre[i] = cur; 
if (i == N + 1){
return flow;
                }
                que[num++] = i;
             }
         }
     }
return -1;
}
void Edmonds_Karp()
{
int maxFlow = 0;
int flow, tmp;
while ((flow = Bfs()) != -1){
           maxFlow += flow;
           tmp = N + 1;
while (tmp != 0){
                 c[pre[tmp]][tmp] -= flow;
                 c[tmp][pre[tmp]] += flow;
                 tmp = pre[tmp];
           }
     }
     printf("%d\n", maxFlow);   
}
int main()
{
    scanf("%d%d", &M, &N);
    CreateGraph();
    Edmonds_Karp();
return 0;
}

第二个：16ms

#include<queue>
#include<stdlib.h>
#include<stdio.h>
using namespace std;

#define NN 104
#define INF 0x5fffffff
int M, N;
int c[NN][NN];
int mark[NN];
int pre[NN];
void CreateGraph()
{
int i, j, cnt, t, x[1004], flag[1004];
for (i = 0; i <= N + 1; i++){
for (j = 0; j <= N + 1; j++){
            c[i][j] = 0;
        }
    }
for (i = 1; i <= M; i++){
        scanf("%d", &x[i]);
        flag[i] = -1; // 标记第i个猪圈刚被哪个商人打开过
    }

for (i = 1; i <= N; i++){
        scanf("%d", &cnt);
for (j = 1; j <= cnt; j++){
            scanf("%d", &t);
if (flag[t] != -1){
                c[flag[t]][i] = INF;
            }else{
                c[0][i] += x[t];
            }
            flag[t] = i;
        }
        scanf("%d", &t);
        c[i][N + 1] = t;
    }
}

int Bfs()
{
int que[NN];
    memset(mark, 0, sizeof(mark));
    mark[0] = 1;
    que[0] = 0;
int cur, i;
int j, num = 1;
for (j = 0; j < num; j++) {
        cur = que[j];
for (i = 0; i <= N + 1; i++){
if (c[cur][i] > 0 && !mark[i]){
                mark[i] = 1;
                pre[i] = cur; 
if (i == N + 1){
return 1;
                }
                que[num++] = i;
            }
        }
    }
return -1;
}
void Edmonds_Karp()
{
int maxFlow = 0;
int flow, tmp;
while (Bfs() == 1){

/*查找最小增流的时候，只查找最短路径上的点*/
        flow = INF;
        tmp = N + 1;
while(tmp != 0){
if (c[pre[tmp]][tmp] < flow){
                flow = c[pre[tmp]][tmp];
            }
            tmp = pre[tmp];
        }
        maxFlow += flow;
        tmp = N + 1;
while (tmp != 0){
            c[pre[tmp]][tmp] -= flow;
            c[tmp][pre[tmp]] += flow;
            tmp = pre[tmp];
        }
    }
    printf("%d\n", maxFlow);   
}
int main()
{
    scanf("%d%d", &M, &N);
    CreateGraph();
    Edmonds_Karp();
//system("pause");
    return 0;
}

两个代码的区别在于，在查找最小的流值的增量时候，第一个是在搜到的所有节点中找，第二个是在最短路径上找的，范围比第一个小，增量就增加的快，BFS的次数就减少了。