POJ 1149PIGS 网络流 最大流

PIGS

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 20421		Accepted: 9320

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 arrives, 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

3 3
3 1 10
2 1 2 2
2 1 3 3
1 2 6

Sample Output

7

---

题目连接：http://poj.org/problem?id=1149

题意：有m个猪圈，n个顾客。下一行输入m个猪圈里面猪的数量。接下来n行，每一行输入a,k1,k2,……,ka,b。表示这个顾客拥有ki猪圈的钥匙，他最多买的猪的数量b。开始时，猪圈是关着的，顾客来购买时，打开所有顾客自己能打开的猪圈，Mirko从中选一些猪卖给顾客，Mirko可以重新分配被打开的猪圈里面的猪。顾客离开后，猪圈关闭。问Mirko最多卖掉多少头猪。

思路：注意因为可以重新分配猪圈里面的猪，网络流的最大流。设置一个源点0和一个汇点n+1，顾客是其他节点。顾客j紧跟在顾客i之后打开某个猪圈，则边<i,j>的容量是+∞。如果某个猪圈是顾客j第一个打开则边<0,j>的容量是这个猪圈的数量。边<j,n+1>的容量是b。

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=1e2+100,INF=1e7+100;
struct Edge
{
    int c,f,g;
} edge[MAXN][MAXN];
int path[MAXN],flow[MAXN];
int sum[1100];
int sign[1100];
queue<int>q;
int bfs(int Start,int End)
{
    int u,v;
    memset(path,-1,sizeof(path));
    memset(flow,0,sizeof(flow));
    while(!q.empty()) q.pop();
    path[Start]=0;
    flow[Start]=INF;
    q.push(Start);
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        if(u==End) break;
        for(v=Start; v<=End; v++)
        {
            if(v!=Start&&path[v]==-1&&edge[u][v].g)
            {
                path[v]=u;
                flow[v]=flow[u]<edge[u][v].g?flow[u]:edge[u][v].g;
                q.push(v);
            }
        }
    }
    return flow[End];
}
int ford(int Start,int End)
{
    int max_flow=0,pre,now,step;
    while((step=bfs(Start,End))!=0)
    {
        max_flow+=step;
        now=End;
        while(now!=Start)
        {
            pre=path[now];
            edge[pre][now].g-=step;
            edge[now][pre].g+=step;
            now=pre;
        }
    }
    return max_flow;
}
int main()
{
    int i,m,n;
    while(~scanf("%d%d",&m,&n))
    {
        for(i=1; i<=m; i++) scanf("%d",&sum[i]);
        for(i=1; i<=n; i++)
        {
            int a,k,b;
            scanf("%d",&a);
            while(a--)
            {
                scanf("%d",&k);
                if(sign[k]==0)
                    edge[sign[k]][i].c+=sum[k];
                else edge[sign[k]][i].c=INF;
                edge[sign[k]][i].g=edge[sign[k]][i].c;
                sign[k]=i;
            }
            scanf("%d",&b);
            edge[i][n+1].g=edge[i][n+1].c=b;
        }
        int Start=0,End=n+1;
        printf("%d
",ford(Start,End));
    }
    return 0;
}