spfa求图的最大流

题目链接：
https://vjudge.net/contest/255738#problem/B
AC代码：
#include <iostream>

#include<vector>

#include<string>

#include<cstring>

#include<queue>

#include<stdio.h>

#define maxn 2000+10

using namespace std;

#define inf 0x3f3f3f3f

int n,m;

vector<pair<int,int > >q[maxn];

int vis[maxn];

int  path[maxn];

int spfa()

{

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

    {

        vis[i]=0;

        path[i]=0;

    }

    path[1]=inf;

    vis[1]=1;

    queue<int>w;

    w.push(1);

    int maxx=0;

    while(!w.empty())

    {

        int top=w.front();

        w.pop();

        vis[top]=0;

        maxx=max(maxx,path[n]);

        if(path[top]<maxx)continue;

        int len=q[top].size();

        for(int i=0; i<len; i++)

        {

            int temp=q[top][i].first;

            if(path[temp]<=path[top])

            if(path[temp]<min(path[top],q[top][i].second)){

            path[temp]=min(path[top],q[top][i].second);

            if(path[temp]>maxx&&vis[temp]==0)

                w.push(temp),vis[temp]=1;

            }

        }

    }

    return maxx;

}

int main()

{

    int T;

    int num=0;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        //  cin>>n>>m;

        for(int i=1; i<=n; i++)q[i].clear();

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

        {

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            q[u].push_back(make_pair(v,w));

            q[v].push_back(make_pair(u,w));

        }

        int ans=spfa();

        printf("Scenario #%d:\n",++num);

        printf("%d\n",ans);

        printf("\n");

        // cout<<"Scenario #"<<++num<<":"<<endl<<ans<<endl;

    }

    return 0;

}
巴特西

spfa求图的最大流

最新文章

热门文章
