首页 > 代码库 > maxflow1149

maxflow1149

自己用DINIC AC的不容易,只出现了一个因为if括号位置不正确导致的错误。

关键是建图

题目大意:有N个顾客,有M个猪圈,每个猪圈有一定的猪,在开始的时候猪圈都是关闭的,

顾客来买书,顾客打开某个猪圈,可以在其中挑选一定的猪的数量,在这个顾客走后,可以在打开的

猪圈中将某个猪圈的一些猪牵到另外一个打开的猪圈,然后所有的猪圈会关闭,这样下一个顾客来了继续上面的工作 

 

 

 

第一行是两个整数:MN1M10001N100

M是猪圈的数目,N是顾客的数目

第二行是M个整数,为每个猪圈中初始猪的数目,范围是[01000]

第三行接下来有N行,每行第一个数A代表第几个顾客会依次打开A个猪圈,

然后跟着有A个数,代表顾客打开的是哪个猪圈,最后有一个数代表这个顾客可以买多少只猪

 

•  每个顾客分别用一个结点来表示。

•  对于每个猪圈的第一个顾客,从源点向他连一条边,容量就是该猪圈里的

猪的初始数量。如果从源点到一名顾客有多条边(因为一个顾客可能同时是几个猪圈的首次访问者),则可以把它们合并成一条,容量相加。

•  对于每个猪圈,假设有n个顾客打开过它,则对所有整数i[1, n),从该

猪圈的第个顾客向第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