uva 10099 The Tourist Guide nyoj 1019 亲戚来了【单个路线最大流【最短路算法】】

分手后的思念是犯贱 2022-08-12 00:09 82阅读 0赞

题目：uva 10099 The Tourist Guide

[nyoj 1019 亲戚来了][nyoj 1019]

题意：给出一个无向图，每条路有一个容量。从 s 到 t 的一条最大的流量。

分析：这个题目可以用最短路的算法来做，最短路是求从 s 到 t 的最短路，这里是求从 s 到 t 的最小容量。最短路的三种算法都可以。

nyoj的使我们比赛的题目，有坑，图有重边，要处理，还有s可能等于t。

spfa代码：

#include <cstdio>
    #include <iostream>
    #include <queue>
    #include <cstring>
    #include <algorithm>
    #include <stack>
    #include <vector>
    #include <utility>
    #include <cmath>
    using namespace std;
    const int N = 120;
    const int inf = 0x3f3f3f3f;
    struct Node
    {
        int v,len;
    };
    vector<Node> v[N];
    void add_Node(int x,int y,int z)
    {
        v[x].push_back((Node){y,z});
        v[y].push_back((Node){x,z});
    }
    void v_clear(int n)
    {
        for(int i=1;i<=n;i++)
            v[i].clear();
    }
    int dis[N];
    void spfa(int s)
    {
        memset(dis,inf,sizeof(dis));
        queue<int> q;
        q.push(s);
        while(!q.empty())
        {
            int tmp=q.front();
            q.pop();
            for(int i=0;i<v[tmp].size();i++)
            {
                Node ff=v[tmp][i];
                int ans=min(dis[tmp],ff.len);
                //printf("--%d %d\n",ff.v,ans);
                if(dis[ff.v]!=inf){
                    if(ans>dis[ff.v])  //注意只要更新了都要压入
                        q.push(ff.v);
                    dis[ff.v]=max(dis[ff.v],ans);
                }
                else
                    q.push(ff.v),
                    dis[ff.v]=ans;
    
            }
        }
    }
    int main()
    {
        int n,m,cas=1;
        while(~scanf("%d%d",&n,&m))
        {
            if(n==0 && m==0)
                break;
            for(int i=0; i<m; ++i){
                int a,b,c;
                scanf("%d%d%d",&a,&b,&c);
                add_Node(a,b,c);
            }
            int s,t,num;
            scanf("%d%d%d",&s,&t,&num);
            spfa(s);
            //printf("%d\n",dis[t]);
            if(dis[t]>=inf)
                printf("-1\n");
            else{
            dis[t]--;
            printf("Scenario #%d\n",cas++);
            printf("Minimum Number of Trips = %d\n\n",(num+dis[t]-1)/dis[t]);}
            v_clear(n);
        }
        return 0;
    }

nyoj floyd 代码：

#include <cstdio>
    #include <iostream>
    #include <queue>
    #include <cstring>
    #include <algorithm>
    #include <stack>
    #include <vector>
    #include <utility>
    #include <cmath>
    using namespace std;
    const int N = 120;
    const int inf = 0x3f3f3f3f;
    int mp[N][N];
    int main()
    {
        int n,m,cas=1;
        while(~scanf("%d%d",&n,&m))
        {
            memset(mp,inf,sizeof(mp));
            for(int i=1;i<=n;i++)
                mp[i][i]=0;
            for(int i=0; i<m; ++i){
                int a,b,c;
                scanf("%d%d%d",&a,&b,&c);
                if(mp[a][b]!=inf)
                    mp[a][b]=mp[b][a]=max(mp[a][b],c);
                else
                    mp[a][b]=mp[b][a]=c;
            }
            int s,t,num;
            scanf("%d%d%d",&s,&t,&num);
            for(int k=1; k<=n; ++k)  //floyd
                for(int i=1; i<=n; ++i){
                    for(int j=1; j<=n; ++j){
                        int tmp = min(mp[i][k], mp[k][j]);
                    if(mp[i][j]==inf) mp[i][j] = tmp;
                    else mp[i][j] = max(mp[i][j],tmp);
                }
            }
            if(s==t)
                puts("0");
            else if(mp[s][t]>=inf)
                printf("-1\n");
            else{
            mp[s][t]--;
            printf("%d\n",(num+mp[s][t]-1)/mp[s][t]);}
        }
        return 0;
    }

nyoj dij代码：

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    const int N = 120;
    const int inf = 0x3f3f3f3f;
    int map[N][N];
    int n,m;
    int dij(int s,int t)
    {
        int vis[N],dis[N];
        memset(vis,0,sizeof(vis));
        memset(dis,-1,sizeof(dis));
        dis[s]=inf;
        //vis[t]=1;
        int tmp=s;
        while(1)
        {
            vis[tmp]=1;
            for(int i=1;i<=n;i++)
            {
                if(map[tmp][i]>0)
                {
                    if(map[tmp][i]>dis[i])
                    {
                        dis[i]=min(dis[tmp],map[tmp][i]);
                    }
                }
            }
            int max=-1;
            for(int i=1;i<=n;i++)
            {
                if(vis[i]==0 && dis[i]>max)
                {
                    max=dis[i];
                    tmp=i;
                }
            }
    //        printf("--%d\n",tmp);
            if(max==-1)
                return dis[t];
        }
    }
    int main()
    {
        while(~scanf("%d%d",&n,&m))
        {
            memset(map,0,sizeof(map));
            for(int i=0;i<m;i++){
                int x,y,z;
                scanf("%d%d%d",&x,&y,&z);
                map[x][y]=max(map[x][y],z);
                map[y][x]=map[x][y];
            }
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            int flow=dij(x,y);
    //        printf("%d\n",flow);
            if(x==y)
            {
                printf("0\n");continue;
            }
            if(flow==-1)
            {
                printf("-1\n");continue;
            }
            int ans=(z-2)/(flow-1)+1;   ///ans=(z-1)/(flow-1);
    //        if((z-1)%(flow-1)!=0 && (z-1)%(flow-1)!=1)
    //            ans++;
            printf("%d\n",ans);
        }
        return 0;
    }

[nyoj 1019]: http://acm.nyist.net/JudgeOnline/problem.php?pid=1019