poj1149 PIGS [最大流]

in 题目 with 0 comment

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


Solution

网络流最大流问题,建图的过程比较玄妙:

  1. 设源点S为0,汇点T为101,其他结点表示顾客
  2. 源点与每个猪圈第一个顾客连边,边权为这个猪圈内猪的数目(如果有重边,则合并边权),故$0\rightarrow i$表示所有猪圈能提供的^(* ̄(oo) ̄)^的数目
  3. 顾客j紧跟在i之后打开猪圈,则连$i\rightarrow j$,边权为INF,因为i开启后与j相关的猪圈中的数目可被随意分配
  4. 每个顾客与T连边,边权为需要买猪的数目

然后用dinic求一遍最大流即可!


Code

#include<bits/stdc++.h>
#define T 101
#define maxn 110
#define maxm 1010
#define maxe 150010
#define INF 0x3f3f3f3f
//#define DEBUG 
using namespace std;
int n,m,cnt=1;
int head[maxn],dis[maxn];
int num_pig[maxm],owner[maxm];

struct edge
{
    int to,next,val;
}e[maxe];

inline int read()
{
    char ch;
    int read=0,sign=1;
    do
        ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-');
    if(ch=='-') sign=-1,ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        read=read*10+ch-'0';
        ch=getchar();
    }
    return sign*read;
}

inline void ins(int u,int v,int w)
{
    ++cnt;
    e[cnt].to=v;
    e[cnt].val=w;   
    e[cnt].next=head[u];
    head[u]=cnt;
}

inline void insert(int u,int v,int w)
{ ins(u,v,w),ins(v,u,0); }

bool bfs()
{
    memset(dis,-1,sizeof(dis));
    queue<int> q;
    q.push(0);
    dis[0]=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        int i=head[u];
        while(i)
        {
            if(dis[e[i].to]==-1&&e[i].val)
                q.push(e[i].to),dis[e[i].to]=dis[u]+1;
            i=e[i].next;
        }
    }
    if(dis[T]==-1) return 0;
    return 1;
}

int dfs(int x,int flow)
{
    if(x==T) return flow;
    int i=head[x],used=0,w;
    while(i)
    {
        if(dis[e[i].to]==dis[x]+1&&e[i].val)
        {
            w=flow-used;
            w=dfs(e[i].to,min(w,e[i].val));
            e[i].val -= w;
            e[i^1].val += w;
            used+=w;
            if(used==flow) return flow;
        }
        i=e[i].next;
    }
    if(!used) dis[x]=-1; 
    return used;
}

int dinic()
{
    int ans=0;
    while(bfs()) ans+=dfs(0,INF);
    return ans; 
}

int main()
{
    memset(owner,-1,sizeof(owner));
    m=read(),n=read();
    for(int i=1;i<=m;++i)
        num_pig[i]=read();
    for(int i=1;i<=n;++i)
    {
        int key=read();
        int w=0;
        for(int j=1;j<=key;++j)
        {
            int x=read();
            if(owner[x]==-1)
              owner[x]=i,w+=num_pig[x];
            else
              insert(owner[x],i,INF);
        }
#ifdef DEBUG
        cerr<<"i="<<i<<"w="<<w<<endl;
#endif
        if(w) insert(0,i,w);
        w=read();
        insert(i,T,w);
    }
#ifdef DEBUG
    for(int i=1;i<=cnt;++i)
        printf("%d-->to=%d ,next=%d ,val=%d \n",i,e[i].to,e[i].next,e[i].val); 
#endif
    printf("%d\n",dinic());
    return 0;
} 

/*
3 3
3 1 10
2 1 2 2
2 1 3 3
1 2 6
-------
7
*/

扫描二维码,在手机上阅读!
Responses