首页 > 代码库 > maxflow1149
maxflow1149
自己用DINIC AC的不容易,只出现了一个因为if括号位置不正确导致的错误。
关键是建图
题目大意:有N个顾客,有M个猪圈,每个猪圈有一定的猪,在开始的时候猪圈都是关闭的,
顾客来买书,顾客打开某个猪圈,可以在其中挑选一定的猪的数量,在这个顾客走后,可以在打开的
猪圈中将某个猪圈的一些猪牵到另外一个打开的猪圈,然后所有的猪圈会关闭,这样下一个顾客来了继续上面的工作
第一行是两个整数:M和N(1≤M≤1000,1≤N≤100)
M是猪圈的数目,N是顾客的数目
第二行是M个整数,为每个猪圈中初始猪的数目,范围是[0,1000]
第三行接下来有N行,每行第一个数A代表第几个顾客会依次打开A个猪圈,
然后跟着有A个数,代表顾客打开的是哪个猪圈,最后有一个数代表这个顾客可以买多少只猪
• 每个顾客分别用一个结点来表示。
• 对于每个猪圈的第一个顾客,从源点向他连一条边,容量就是该猪圈里的
猪的初始数量。如果从源点到一名顾客有多条边(因为一个顾客可能同时是几个猪圈的首次访问者),则可以把它们合并成一条,容量相加。
• 对于每个猪圈,假设有n个顾客打开过它,则对所有整数i∈[1, n),从该
猪圈的第i 个顾客向第i + 1 个顾客连一条边,容量为∞。
• 从各个顾客到汇点各有一条边,容量是各个顾客能买的数量上限。
#include<cstdio>
#include<cstring>
#define MAXV 9999
int pig[1002],consumer[102];
int map[105][105];
int pigfirst[1002];
int sp,fp;
int maxflow;
int que[105],front,back;
int d[105];
int low[105];
int n;
int cmpmin(int a,int b)
{
return a<b?a:b;
}
int bfs()
{
int i;
memset(que,0,sizeof(que));
memset(d,0,sizeof(d));
d[0]=1;
front=0;
back=1;
que[front]=0;
int temp;
while(front!=back)
{
temp=que[front++];
for(i=1;i<=n+1;i++)
if(map[temp][i]>0 && d[i]==0)
{
d[i]=d[temp]+1;
que[back++]=i;
}
}
if(d[fp]==0)
return 0;
else return 1;
}
int dfs(int start,int flow)
{
if(start==n+1)
return flow;
int i,temp=flow;
int t;
for(i=1;i<=n+1;i++)
{
if(d[start]+1==d[i] && map[start][i]>0 && temp)
{
t=dfs(i,cmpmin(temp,map[start][i]));
map[start][i]-=t;
map[i][start]+=t;
temp-=t;
}
}
return flow-temp;
}
void dinic()
{
while(bfs()) maxflow+=dfs(0,99999);
}
int main()
{
int m,temp,temp2,temp3,i,j;
while(scanf("%d%d",&m,&n)!=EOF)
{
memset(map,0,sizeof(map));
memset(pigfirst,0,sizeof(pigfirst));
maxflow=0;
for(i=1;i<=m;i++)
scanf("%d",&pig[i]);
sp=0;
fp=n+1;
for(i=1;i<=n;i++)
{
scanf("%d",&temp);
for(j=1;j<=temp;j++)
{
scanf("%d",&temp2);
if(pigfirst[temp2]==0)
{
pigfirst[temp2]=i;
map[sp][i]+=pig[temp2];
}
else
{
map[pigfirst[temp2]][i]=MAXV;
}
}
scanf("%d",&temp3);
map[i][fp]=temp3;
}
dinic();
printf("%d\n",maxflow);
}
return 1;
}
maxflow1149