poj1273最大流初破

第一次网络流，学了一天的DINIC算法（个人比较愚），切了这个入门题，开始的时候怎么调连

测试都过不了，后来发现犯了一个低级错误！把判断条件放在for（；）!里面和放在for下面大大

不同啊！里面的话，一遇到不符合立即结束了（相当于break）！而下面的可以continue！

dinic算法，每次BFS根据残量网络作层次图，每做一次后DFS找一个增广路（我是到目标点就return，

每次记录该增广路中的最窄边，回溯时按最窄边更新图即可）。

#include<iostream>  //16ms 1A

#include<vector>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int inf=0x3f3f3f3f;

int m,n;

struct edge

{

    int to,f,pre;

};

int mark=0;int minf=inf;             //一条增广路最窄的边

int head[201];vector<edge>edges(403);

int vis[201];int level[201];

bool bfs()                         //层次图，根据残量网络记录与原点的距离（层次）

{

    for(int i=1;i<=n;i++)

    {

        vis[i]=level[i]=0;

    }

    vis[1]=1;

    queue<int>q;q.push(1);

    while(!q.empty())

    {

        int cur=q.front();

        q.pop();

        for(int i=head[cur];i!=-1;i=edges[i].pre)

        {

           if(edges[i].f>0&&!vis[edges[i].to])  //放里面

           {

            vis[edges[i].to]=1;

            q.push(edges[i].to);

            level[edges[i].to]=level[cur]+1;

           }

        }

    }

    return vis[n];          //访问不到目标地，结束（找不到增广路）

}

void dfs(int cur)           //每次找一条增广路

{

    if(cur==n||mark){mark=1;return;}

    for(int i=head[cur];i!=-1&&!mark&&minf;i=edges[i].pre)

    {

        int v=edges[i].to;

        int temp=edges[i].f;

        if(level[v]==level[cur]+1&&temp)

        {

            int tmin=minf;

            if(minf>temp)minf=temp;

            dfs(v);

           if(mark)

           {

            edges[i].f-=minf;

            edges[i^1].f+=minf;

           }

           else               //非目的地的回溯，minf作为全局变量，要改回来。

              minf=tmin;

        }

    }

    return ;

}

int main()

{

    while(~scanf("%d%d",&m,&n))

    {

        int s,l,c;

        memset(head,-1,sizeof(head));

        for(int i=0;i<2*m;i++)

        {

            scanf("%d%d%d",&s,&l,&c);

            edges[i].to=l;

            edges[i].pre=head[s];

            head[s]=i;edges[i].f=c;

            i++;

             edges[i].to=s;

            edges[i].pre=head[l];

            head[l]=i;edges[i].f=0;

        }

        long long maxflow=0;

        while(bfs())

        {

            mark=0;minf=inf;

            dfs(1);

            maxflow+=minf;

        }

        printf("%lld\n",maxflow);

    }

}

巴特西

poj1273最大流初破

最新文章

热门文章