POJ 1149PIGS 网络流 最大流

时间：2023-03-09 00:35:34
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+,INF=1e7+;

struct Edge

{

    int c,f,g;

} edge[MAXN][MAXN];

int path[MAXN],flow[MAXN];

int sum[];

int sign[];

queue<int>q;

int bfs(int Start,int End)

{

    int u,v;

    memset(path,-,sizeof(path));

    memset(flow,,sizeof(flow));

    while(!q.empty()) q.pop();

    path[Start]=;

    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]==-&&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=,pre,now,step;

    while((step=bfs(Start,End))!=)

    {

        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=; i<=m; i++) scanf("%d",&sum[i]);

        for(i=; i<=n; i++)

        {

            int a,k,b;

            scanf("%d",&a);

            while(a--)

            {

                scanf("%d",&k);

                if(sign[k]==)

                    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+].g=edge[i][n+].c=b;

        }

        int Start=,End=n+;

        printf("%d\n",ford(Start,End));

    }

    return ;

}

最大流

相关文章