poj1149（标号法）

PIGS

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 14239		Accepted: 6330

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

Sample Output

#include <cstdio>
#include <cstring>
#define INF 300000000    //无穷大
#define MAXM 1000        //猪圈数：1≤M≤1000
#define MAXN 100        //顾客数：1≤N≤100

int s, t;    //源点，汇点
int customer[MAXN+2][MAXN+2];    //N+2个结点(包括源点,汇点)之间的容量Cij
int flow[MAXN+2][MAXN+2];    //节点之间的流量Fij
int i, j;    //循环变量

void init( )    //初始化函数，构造网络流
{
    int M, N;    //M是猪圈的数目，N是顾客的数目
    int num;    //每个顾客拥有钥匙的数目
    int k;        //第K个猪圈的钥匙
    int house[MAXM];    //存储每个猪圈中猪的数目
    int last[MAXM];        //存储每个猪圈的前一个顾客的序号
    memset( last, 0, sizeof(last) );  memset( customer, 0, sizeof(customer) );
    
    scanf( "%d%d", &M, &N );
    s = 0;  t = N + 1;    //源点、汇点
    
    for( i=1; i<=M; i++ )    //读入每个猪圈中猪的数目
        scanf( "%d", &house[i] );
    for( i=1; i<=N; i++ )    //构造网络流
    {      
        scanf( "%d", &num );    //读入每个顾客拥有钥匙的数目
        for( j=0; j<num; j++ )
        {
            scanf( "%d", &k );    //读入钥匙的序号
            if( last[k]==0 )    //第i个顾客是第k个猪圈的第1个顾客
                customer[s][i] = customer[s][i] + house[k];
            else    //last[k]!=0,表示顾客i紧跟在顾客last[k]后面打开第k个猪圈
                customer[ last[k] ][i] = INF;
            last[k] = i;
        }
        scanf( "%d", &customer[i][t] );    //每个顾客到汇点的边,权值为顾客购买猪的数量
    }
}

void ford( )
{
    //可改进路径上该顶点的前一个顶点的序号,相当于标号的第一个分量,
    //初始为-2表示未标号,源点的标号为-1
    int prev[ MAXN+2 ];
    int minflow[ MAXN+2 ]; //每个顶点的可改进量α，相当于标号的第二个分量

    //采用广度优先搜索的思想遍历网络，从而对所有顶点进行标号
    int queue[MAXN+2];    //相当于BFS算法中的队列
    int qs, qe;            //队列头位置、队列尾位置
    int v;                //当前检查的顶点
    int p;                //用于保存Cij-Fij
    for( i=0; i<MAXN+2; i++ )    //构造零流:从零流开始标号调整
    {
        for( j=0; j<MAXN+2; j++ )  flow[i][j] = 0;
    }
    minflow[0] = INF;    //源点标号的第二个分量为无穷大

    while( 1 ) //标号法
    {
        for( i=0; i<MAXN+2; i++ )    //每次标号前，每个顶点重新回到未标号状态
            prev[i] = -2;
        prev[0] = -1;        //源点
        qs = 0;  queue[qs] = 0;  qe = 1;    //源点(顶点0)入队列

        //标号过程：如果qe>=qs(相当于队列空)，标号也无法再进行下去
        while( qs<qe && prev[t]==-2 )
        {
            v = queue[qs];  qs++;    //取出队列头顶点
            for( i=0; i<t+1; i++ )
            {
                //如果顶点i是顶点v的"邻接"顶点，则考虑是否对顶点i进行标号
                //customer[v][i]-flow[v][i]!=0能保证顶点i是v的邻接顶点,
                //且能进行标号
                //顶点i未标号，并且Cij-Fij>0
                if( prev[i]==-2 && ( p=customer[v][i]-flow[v][i]) )
                {
                    prev[i] = v;  queue[qe] = i;  qe++;
                    minflow[i] = (minflow[v]<p) ? minflow[v] : p;  
                }
            }
        }
        
        if( prev[t] == -2 )  break;    //汇点t没有标号，标号法结束

        for( i=prev[t], j=t; i!=-1; j=i, i=prev[i] )    //调整过程
        {
            flow[i][j] = flow[i][j] + minflow[t];
            flow[j][i] = -flow[i][j];
        }
    }
    for( i=0, p=0; i<t; i++ )    //统计进入汇点的流量，即为最大流的流量
        p = p + flow[i][t];
    printf( "%d
", p );
}

int main( )
{
    init( );
    ford( );
    return 0;
}