poj 1149 Pigs(最大流)

解题思路

题意：

       有m个猪房，先后来了n个顾客来买猪，分别打开A个猪房，买到自己需要的猪，然后关门。当门打开的时候Mirko可以把剩下的猪随意换房间。问最多可以卖出多少头猪。

 

思路：

       这个问题建图很难想到，参考网上的思路才会做。

假设访问第i个猪圈顾客依次为Pi1，Pi2，Pi3，……Pi(J)……

1.先让N个顾客对应N个节点， 

  则在Pi(J-1)和Pi(J)之间连接容量为MAXF(无穷大）的边；(1<=i<=m)

2.源点S到Pi1连接边，

  容量为第I个猪圈中猪的数目，并合并重边（容量相加）；(1<=i<=m)

3.N个节点到汇点T连接边，容量为每个顾客愿意购买的猪的数量。

是一共有n+2个结点的网络求最大流，到达汇点T的流量和即为最优解。

 

推荐看这篇解题报告，讲得非常清楚：

源程序

 

#include <stdio.h>
#include <string.h>
#include <conio.h>
#define inf 100000000
#define N 105
#define M 1005
int map[N][N], pre[N], d[N], num[N];
int g[M][N];
int n;
int find(int i)
{
    int j;
    for(j=1; j<=n; j++)
    {
        if(map[i][j] > 0 && d[i] == d[j] + 1)
            return j;
    }
    return -1;
}

int relable(int i)
{
    int mm = inf, j;
    for(j=1; j<=n; j++)
    {
        if(map[i][j] > 0)
            mm = mm < d[j] + 1 ? mm : d[j] + 1;
    }
    return mm == inf ? n : mm;
}

int maxflow(int s, int t)
{
    int i, j, k, x, flow;
    memset(pre, -1, sizeof(pre));
    flow = 0;
    i = s;
    while(d[s] < n)
    {
        j = find(i);
        if(j > 0)
        {
            pre[j] = i;
            i = j;
            if(i == t)
            {
                x = inf;
                for(k=t; k!=s; k=pre[k])
                    x = x < map[pre[k]][k] ? x : map[pre[k]][k];
                for(k=t; k!=s; k=pre[k])
                {
                    map[pre[k]][k] -= x;
                    map[k][pre[k]] += x;
                }
                flow += x;
                i = s;
            }
        }
        else
        {
            x = relable(i);
            num[x]++;
            num[d[i]]--;
            if(num[d[i]] == 0)
                return flow;
            d[i] = x;
            if(i != s)
                i = s;
        }
    }
    return flow;
}

int main()
{
    int i, j, k, x, y;
    int p; //pighouse

    int c;    //customer

    int pigs[M];
    int buy[N];
    
    freopen("in.txt", "r", stdin);
    scanf("%d%d", &p, &c);
    for(i=1; i<=p; i++)
    {
        scanf("%d", &pigs[i]);
    }
    for(i=1; i<=c; i++)
    {
        scanf("%d", &x);
        for(j=1; j<=x; j++)
        {
            scanf("%d", &y);
            g[y][++g[y][0]] = i;
        }
        scanf("%d", &buy[i]);
    }
    for(i=1; i<=p; i++)
    {
        map[c+1][g[i][1]] += pigs[i];
        for(j=2; j<=g[i][0]; j++)
            map[g[i][j-1]][g[i][j]] = inf;
    }
    for(i=1; i<=c; i++)
        map[i][c+2] = buy[i];
    n = c+2;
    printf("%d\n", maxflow(n-1, n));
    getch();
    return 0;
}

Memory： 616KB  Time： 0MS