PIGS
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 18727 | Accepted: 8508 |
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.
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.
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
网络流问题的难点还是在于建图
题意：一个工人在养猪场工作，他负责卖猪，现在有m个猪圈和n个顾客，每个猪圈的容量没有限制，但是工人没有猪圈的钥匙，而前来的顾客有这些猪圈中一些猪圈的钥匙，每个顾客来之后会打开所有他有钥匙的猪圈，然后买完自己想要买的猪的个数后，关闭所有他打开的猪圈，顾客总是一个接一个的来，当猪圈打开的时候，工人可以随意挪动打开的猪圈中的猪（只能在打开的猪圈中相互移动）问工人一天最多卖出去多少猪
输入：开头第一行两个整数m，n分别代表猪圈数和顾客数，接下来一行m个数分别表示对应的猪圈中猪的个数，在接下来n行每行第一个数a，表示接下来a个数意思是当前行（第i行）i顾客所持的猪圈的钥匙，最后一个数b代表这个顾客要买b头猪
题解：1、超级源点连接第一个到达j猪圈的顾客 权值为第j个猪圈的猪的头数，
2、因为每个同时打开的猪圈之间的猪可以相互走动，所以所有连接到j猪圈的顾客相互连接容量为无穷大
3、处理重边，比如说第一个猪圈的第一个顾客和第二个猪圈的第一个顾客都是cus1，第三个猪圈的第一个顾客是cus2，所以就有源点到cus1的重边，此时将这两条边合并即可，流量为二者流量和
4、每一个顾客连接超级汇点
#include<stdio.h>
#include<string.h>
#include<stack>
#include<queue>
#include<algorithm>
#include<vector>
#define MAXM 100100
#define MAX 10010
#define INF 0x7ffff
using namespace std;
vector<int>map[MAXM];
int n,m,a,b[MAX];
int ans,head[MAX];
int cur[MAX],dis[MAX];
int vis[MAX];
int pig[MAX];
struct node
{
int from,to,cap,flow,next;
}edge[MAXM];
void init()
{
ans=0;
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++)
map[i].clear();
}
void add(int u,int v,int w)
{
int i,j;
for(i=head[u];i!=-1;i=edge[i].next)
{
if(edge[i].to==v) //判断是否有重边
break;
}
if(i==-1)//i==-1表示当前这个点并没有边与其相连
{
edge[ans]={u,v,w,0,head[u]};
head[u]=ans++;
edge[ans]={v,u,0,0,head[v]};
head[v]=ans++;
}
else//如果有重边 则将流量合并
if(w!=INF)
edge[i].cap+=w;
}
void input()
{
int i,j,key;
for(i=1;i<=m;i++)
scanf("%d",&pig[i]);
for(i=1;i<=n;i++)
{
scanf("%d",&a);
while(a--)
{
scanf("%d",&key);
map[key].push_back(i);//存储先后到第可以个猪圈的顾客编号
}
scanf("%d",&b[i]);
}
}
void getmap()
{
int i,j;
for(i=1;i<=m;i++)
{
int u=map[i][0];
add(0,u,pig[i]);//超级源点连接第一个到i猪圈的顾客
for(j=0;j<map[i].size()-1;j++)
add(map[i][j],map[i][j+1],INF);//所有到i猪圈的顾客按照顺序连接
}
for(i=1;i<=n;i++)
add(i,n+1,b[i]);//所有顾客连接汇点
}
int bfs(int beg,int end)
{
int i;
memset(vis,0,sizeof(vis));
memset(dis,-1,sizeof(dis));
queue<int>q;
while(!q.empty())
q.pop();
vis[beg]=1;
dis[beg]=0;
q.push(beg);
while(!q.empty())
{
int u=q.front();
q.pop();
for(i=head[u];i!=-1;i=edge[i].next)//遍历所有的与u相连的边
{
node E=edge[i];
if(!vis[E.to]&&E.cap>E.flow)//如果边未被访问且流量未满继续操作
{
dis[E.to]=dis[u]+1;//建立层次图
vis[E.to]=1;//将当前点标记
if(E.to==end)//如果当前点搜索到终点则停止搜索 返回1表示有从原点到达汇点的路径
return 1;
q.push(E.to);//将当前点入队
}
}
}
return 0;//返回0表示未找到从源点到汇点的路径
}
int dfs(int x,int a,int end)//把找到的这条边上的所有当前流量加上a（a是这条路径中的最小残余流量）
{
//int i;
if(x==end||a==0)//如果搜索到终点或者最小的残余流量为0
return a;
int flow=0,f;
for(int& i=cur[x];i!=-1;i=edge[i].next)//i从上次结束时的弧开始
{
node& E=edge[i];
if(dis[E.to]==dis[x]+1&&(f=dfs(E.to,min(a,E.cap-E.flow),end))>0)//如果
{//bfs中我们已经建立过层次图，现在如果 dis[E.to]==dis[x]+1表示是我们找到的路径
//如果dfs>0表明最小的残余流量还有，我们要一直找到最小残余流量为0
E.flow+=f;//正向边当前流量加上最小的残余流量
edge[i^1].flow-=f;//反向边
flow+=f;//总流量加上f
a-=f;//最小可增流量减去f
if(a==0)
break;
}
}
return flow;//所有边加上最小残余流量后的值
}
int Maxflow(int beg,int end)
{
int flow=0;
while(bfs(beg,end))//存在最短路径
{
memcpy(cur,head,sizeof(head));//复制数组
flow+=dfs(beg,INF,end);
}
return flow;//最大流量
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF)
{
init();
input();
getmap();
printf("%d
",Maxflow(0,n+1));
}
return 0;
}