轉載請注明出處: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);
}