POJ 1149 PIGS//MAXFLOW

PIGS
Time Limit: 1000MS
 
Memory Limit: 10000K
Total Submissions: 7773
 
Accepted: 3367
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

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

Sample Output

7

Source
Croatia OI 2002 Final Exam - First day
 
 
1) 고객마다 각각 하나의 노드로 표시한다.2) 모든 돼지우리에 대한 첫 번째 고객은 원점에서 그에게로 연결되어 용량이 바로 이 돼지우리에 있는 돼지의 초기 수량이다.만약 원점에서 고객 한 명까지 여러 개의 변이 있다면, 그것들을 하나로 합쳐서 용량을 더할 수 있다.3) 각 돼지우리에 대해 n명의 고객이 그것을 열었다고 가정하면 모든 정수 i∈[1,n), 이 돼지우리의 i번째 고객으로부터 i+1명의 고객에게 한 가닥을 연결한다. 용량은 +∞이다. 4) 각 고객부터 외환점까지 각각 한 가닥이 있고 용량은 각 고객이 살 수 있는 수량 상한선이다.
 
#include
#include
#include
using namespace std;
const int inf=100000000;
 
int n,m,flow[110][110],dist[110],gap[110];//주의 범위
int find_path(int p, int limit = 0x3f3f3f3f)
{
    if (p == n - 1) return limit;
    for (int i = 0; i < n;++i)
    {
        if (dist[p] == dist[i] + 1 && flow[p][i] > 0)
        {
            int t = find_path(i, min(limit, flow[p][i]));
            if (t < 0) return t;
            if (t > 0)
            {
                flow[p][i] -= t;
                flow[i][p] += t;
                return t;
            }
        }
    }
    int label = n;
    for (int i = 0; i < n;++i) if (flow[p][i] > 0)  label = min(label, dist[i] + 1);
    if (--gap[dist[p]] == 0 || dist[0] >= n) return -1;
    ++gap[dist[p] = label];
    return 0;
}
int iSAP()
{
    gap[0] = n;
    int maxflow = 0,t = 0;
    while ((t = find_path(0)) >= 0)  maxflow += t;
    return maxflow;
}
int ph[1001];
bool vis[1001];
int main()
{
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        memset(flow,0,sizeof(flow));
        memset(gap,0,sizeof(gap));
        memset(dist,0,sizeof(dist));//초기화 주의
        memset(vis,false,sizeof(vis));
        for(int i=1;i<=m;i++) scanf("%d",&ph[i]);
        int k,t,a;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&k);
            for(int j=1;j<=k;j++)
            {
                scanf("%d",&a);
                if(!vis[a])
                {
                    flow[0][i]+=ph[a];
                    vis[a]=true;
                    ph[a]=i;
                }
                else
                {
                    flow[ph[a]][i]=inf;
                    ph[a]=i;
                }
            }
            scanf("%d",&t);
            flow[i][n+1]=t;
        }
        n=n+2;
        printf("%d/n",iSAP());
    }
    return 0;
}