转载请注明出处:http://www.klion.0fees.net/?p=33

这题是一个网络流的入门题,由于点和边都不多,所以可以直接用Edmond-Karp算法解决。另外HDU3549也可以用EK算法直接过掉

对于Edmond-Karp算法就是每次用bfs找增广路径,然后改变相应的残留网络就ok了,不过这题要注意的就是两个点之间不一定只有一条边,所以要把所有边都加起来才行。这里贴一下关键代码:

int bfs(int s,int t,int total)
{//这里s是起点 t是终点 total是总的顶点数
int front,rear,u,v;
int q[206*206];//队列 可以不用开这么大 
memset(pre,-1,sizeof(pre));
front = rear = -1;
rear++;
q[rear] = s;
while(front < rear)
{//bfs找增广路径
front++;
u = q[front];
for(v = 1;v <= total;v++)
{
if(-1 == pre[v] && num[u][v] > 0)
{
pre[v] = u;
rear++;
q[rear] = v;
if(v == t)//如果找到了汇点就直接推出
return 1;
}
}
}
return 0;
}
void work()
{
int u,v,inc,maxflow;
maxflow = 0;//初始化流量为0
while(1)
{
if(!bfs(1,m,m))//如果不存在增广路径 也就是说当前流量为最大流了
{
break;
}
inc = 99999999;
for(v = m;v != 1;v = u)
{//找这条增广路径能增加的最小流量
u = pre[v];
if(num[u][v] < inc)
inc = num[u][v];
}
for(v = m;v != 1;v = u)
{//改变残留网络
u = pre[v];
num[u][v] -= inc;  //这条边的流量减少inc
num[v][u] += inc;  //反向边的流量增加inc
}
maxflow += inc;//增加网络流的值
}
printf("%d\n",maxflow);
}