IT博客汇 | poj 1149——PIGS 卖猪最大流

poj 1149——PIGS 卖猪最大流

火碳黑发表于 2011-04-13 02:47:00

PIGS

Description

Mirko works on a pig farm that consists of M locked pig-houses and Mirko can't unlock any pighouse because he doesn't have the keys. Customers come to the farm one after another. Each of them has keys to some pig-houses and wants to buy a certain number of pigs.
All data concerning customers planning to visit the farm on that particular day are available to Mirko early in the morning so that he can make a sales-plan in order to maximize the number of pigs sold.
More precisely, the procedure is as following: the customer arives, opens all pig-houses to which he has the key, Mirko sells a certain number of pigs from all the unlocked pig-houses to him, and, if Mirko wants, he can redistribute the remaining pigs across the unlocked pig-houses.
An unlimited number of pigs can be placed in every pig-house.
Write a program that will find the maximum number of pigs that he can sell on that day.

Input

The first line of input contains two integers M and N, 1 <= M <= 1000, 1 <= N <= 100, number of pighouses and number of customers. Pig houses are numbered from 1 to M and customers are numbered from 1 to N.
The next line contains M integeres, for each pig-house initial number of pigs. The number of pigs in each pig-house is greater or equal to 0 and less or equal to 1000.
The next N lines contains records about the customers in the following form ( record about the i-th customer is written in the (i+2)-th line):
A K1 K2 ... KA B It means that this customer has key to the pig-houses marked with the numbers K1, K2, ..., KA (sorted nondecreasingly ) and that he wants to buy B pigs. Numbers A and B can be equal to 0.

Output

The first and only line of the output should contain the number of sold pigs.

Sample Input

Sample Output

7
题意：
有农民在卖猪，有M个猪笼，每个人有某些猪笼的钥匙，所以每个人可以买他能打开的猪笼中的猪，人是按顺序买猪的，当第i-1个人买完后，
他能打开的猪笼可以中的猪可以被重新调整。就是在那些猪笼中移动猪。
给出每个猪笼的猪数量，给出每个人能打开的猪笼序号以及想购买的猪数量。
求：最多能卖多少猪。
分析：主要是怎么弄让被打开过的猪笼可以移动猪。如果i跟i+1两个人的钥匙没交集，则他们只能买自己的猪笼端的猪，如果两个人有交集，
那i+1的可以买i能打开的猪笼x的猪，i可以连向x，边的流量正无穷。
代码：


#include <iostream>
#include <stdlib.h>
using namespace std;
const int maxn= 20010;
const int M = 1010;
const __int64 inf=0x7fffffff;
struct node
{
    __int64 v,next;
    __int64 w;
}fn[500010];
__int64 level[maxn],g[maxn],que[maxn],out[maxn], th, tip, visit[maxn];
__int64 key[M][M], h[M], buy[M], hash[M][M], len[M];
inline void add(__int64 u,__int64 v,__int64 w)
{
    fn[th].v = v, fn[th].w = w, fn[th].next = g[u], g[u] = th++;    
    fn[th].v = u, fn[th].w = 0, fn[th].next = g[v], g[v] = th++;
}
void build_level(__int64  n,__int64 s,__int64  e)
{
    __int64 h=0,r=0,i,u;    
    for (i = 0; i <= n; i++) level[i]=0;
    level[s] = 1;
    que[0] = s;
    while(h <= r)
    {
        u = que[h++];
        for (i = g[u]; i != -1; i = fn[i].next)
        {
            if (fn[i].w && level[fn[i].v] == 0)
            {
                que[++r] = fn[i].v;
                level[fn[i].v] = level[u] + 1;
             }
        }
    }
 }
__int64 dinic(__int64 n,__int64 s,__int64 e)
{
    __int64 ret=0,i;
    while(1)
    {
        build_level(n,s,e);
        if (level[e] == 0) break;
        for (i = 0; i < n; ++i) out[i] = g[i];
        __int64 q = -1;
        while(1)
        {
            if (q < 0)
            {
                for (i = out[s]; i != -1; i = fn[i].next)
                {
                    if (fn[i].w && out[fn[i].v] != -1 && level[fn[i].v] == 2)
                    {
                        que[++q] = i;
                        out[s] = fn[i].next;
                        break;
                    }
                }
                if (i == -1)
                {
                    break;
                }
            }
            __int64 u = fn[que[q]].v;
            if(u == e)
            {
                __int64 tmp=inf;
                for(i = 0;i <= q; i++)
                    if(tmp > fn[que[i]].w)tmp = fn[que[i]].w;
                ret += tmp;
                for(i=0;i<=q;i++)
                {
                    fn[que[i]].w -= tmp;
                    fn[que[i]^1].w += tmp;   
                }
                for (i = 0; i <= q; i++)
                {
                    if(fn[que[i]].w == 0)
                    {
                        q = i-1;
                        break;
                    }
                }
            }
            else
            {
                for (i = out[u]; i != -1; i = fn[i].next)
                {
                    if (fn[i].w && out[fn[i].v] !=-1 && level[u] + 1 == level[fn[i].v]) 
                    {
                        que[++q] = i, out[u] = fn[i].next;
                        break;
                    }
                }
                if(i==-1)
                {
                    out[u] = -1, q--;
                 }
              
            }
        }
    }
    return ret;
}
int main()
{
    __int64 m, n, s, t, i, j, k;
    scanf("%I64d%I64d", &m, &n);
    s = 0, t = n + m + 1;
    for (i = 0; i < t + 10; i++)
    {
        g[i] = -1;
    }
    for (i = 1; i <= m; i++)
    {
        scanf("%I64d", &h[i]);
        add(i + n, t, h[i]);
    }
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
        {
            hash[i][j] = 0;
        }
    }
    for (i = 1; i <= n; i++)
    {
        scanf("%I64d", &len[i]);
        for (j = 0; j < len[i]; j++)
        {
            scanf("%I64d", &key[i][j]);
            hash[i][key[i][j]] = 1;
        }
        scanf("%I64d", &buy[i]);
        add(0, i, buy[i]);
    }
    for (i = 1; i <= n; i++)
    {
        for (j = 0; j < len[i]; j++)
        {
            add(i, key[i][j] + n, inf);
        }
        for (j = 0; j < i; j++)//对前i-1的人，有钥匙交集的，i可以买他们能打开的猪笼
        {
            if (i != j)
            {
                for (k = 0; k < len[i]; k++)
                {
                    if (hash[j][key[i][k]])
                    {
                        break;
                    }
                }
                if (k != len[i])
                {
                    for (k = 0; k < len[j]; k++)
                    {
                        add(i, key[j][k] + n, inf);    
                    }
                }
            }
        }
        
    }
    printf("%I64d\n", dinic(t + 1, s, t));
    return 0;
}

火碳黑 2011-04-13 10:47 发表评论