USACO 4-2-1Drainage Ditches

一个入门的网络流题目,由于点和边都不多,所以我用了原始的EK算法(其实当时我也只会这最原始的算法),也就是每次用bfs找增广路,复杂度是O(V*E^2)。下面直接给出代码

/
  LANG:C
  TASK:ditch
  ID:qcx97811
/
#include 
#include 
#include 

int graph[206][206],pre[206];//graph是原图,pre是用来存每个点的前驱的
int N,M,maxflow//N和M是题中的 maxlfow就是结果了

int bfs()
{
    int i,j
    int q[206];
    int front,rear
    memset(pre,-1,sizeof(pre));
    front = rear = -1
    q[++rear] = 1
    while(front < rear)//bfs找一条从源点到汇点的路径
        {
            i = q[++front];
            for(j = 1j <= M;j++)
                {
                    if(-1 == pre[j] & graph[i][j] > 0)
                        {//如果当前点没有没用而且可用
                            pre[j] = i
                            rear++
                            q[rear] = j
                            if(j == M)//如果已经到了汇点 也就是已经找到一条增广路径
                                return 1
                        }
                }
        }
    return 0
}
void max_flow()
{
    int i,j,add
    maxflow = 0
    while(0 != (add = bfs()))
        {//如果还有增广路径
            add = 10000006
            for(i = Mi != 1;i = pre[i])
                {//找出本次能增广的最大流量
                    j = pre[i];
                    if(graph[j][i] < add)
                        add = graph[j][i];
                }
            for(i = Mi != 1;i = pre[i])
                {//改变残留网络
                    j = pre[i];
                    graph[j][i] -= add
                    graph[i][j] += add
                }
            maxflow += add//更改结果
        }
}
int main(void)
{
    freopen(“ditch.in”,“r”,stdin);
    freopen(“ditch.out”,“w”,stdout);
    int i,s,e,c
    scanf(“%d%d”,N,&M);
    memset(graph,0,sizeof(graph));
    //下面是建图
    for(i = 0i < N;i++)
        {
            scanf(“%d%d%d”,s,&e,&c);
            graph[s][e] += c
        }
    max_flow();//调用max_flow得到结果
    printf(“%d\n“,maxflow);
    return 0
}

Enjoy it ? Donate me ! 欣赏此文？支持一下呗

USACO 4-2-1Drainage Ditches

Comments