| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 18727 | Accepted: 8508 |
Description
Input
Output
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\n",Maxflow(0,n+1));
}
return 0;
}
原文：http://www.cnblogs.com/tonghao/p/4939984.html