问题

一个计算机网络,计算机为节点,连接他们的线为无向边,每条边有一个流量上限。求从计算机s到t的最大带宽。s发出流量,t接收流量,且流量不能被分割,也就是说最后找到的最大带宽路径是一条路,而不能像网络流一样。

输入格式
第一行,四个正整数 n, m, s, t,分别代表计算机数量,直接链路数量,起点编号和终点编号。

接下来 m 行,第 i 行包含三个正整数 ui, vi, wi,表示从ui到vi的链路是第 i 条直接链路,最大带宽为wi。

输出格式
输出一个正整数,表示指定的两台计算机通信时的最大可能带宽(单位:Mbps)。

样例输入

4 5 1 4
1 2 3
1 3 6
2 3 4
2 4 5
3 4 3

样例输出

8

建模

问题是在简单图中寻找从s到t的最大带宽路径。即要使这条路径中最小容量的边的容量极大。

算法

由于流量不能被计算机节点拆分传输,因此类似于最大流但是又不是最大流。由于所求解是一条“单源最优路径”,类似于“单源最短路径”,因此考虑Dijkstra算法。但是原算法所求为总长最短,现在是要求路径中最小容量的边的容量尽可能大,因此只需修改Dijkstra算法中选优的部分与更新最优值的部分即可。

具体来说就是,类似于原算法同样维护两个节点集viewed和not_viewed,维护每个节点的一个标记,内容为它的前驱(p)和从s到它时的最大带宽(w)。初始时从s点开始走,并将s加入viewed。每次遍历not_viewed中的点,选择与viewed相连的点中连接的边的容量最大的点作为k(修改之一),然后在k处更新k的邻点集中节点的信息。更新方法为,设遍历k的邻点j,比较 delta = min(k的标记中的w值, 边(k, j)的容量)与j的标记中的w值,如果前者大于后者,则将j的标记中的w值更新为前者,同时前驱设为k。这样就找到了从s到j的带宽更大的一条路径。重复上述操作,直到not_viewed中没有点。(实际上可以知道重复了n-1次。)

最终答案就是点t的标记中的w值。

实现

//
//  main.cpp
//  t3
//
//  Created by Colin on 2020/05/01.
//  Copyright © 2020 Colin. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

const int maxn = 102;

class Dijkstra_maxflow
{
public:
    int (*graph)[maxn];
    int n, m, s, t;
    int dist[maxn];
    int pre[maxn];
    const int max_w = 0x7ffffff;
    
    Dijkstra_maxflow(const int _n, const int _m, const int _s, const int _t, int (*_g)[maxn]):
        n(_n), m(_m), s(_s), t(_t), graph(_g)
    {
        memset(dist, 0, sizeof(dist));
        for (int j = 1; j <= n; j++)
        {
            dist[j] = graph[s][j];
        }
    }
    
    int min(const int _a, const int _b)
    {
        return _a < _b ? _a : _b;
    }
    
    void work()
    {
        bool viewed[maxn] = { 0 };
        viewed[s] = 1;
        dist[s] = max_w;
        for (int i = 1; i <= n - 1; i++)
        {
            // find the not-viewed point which linked to viewed points having the max flow
            int tmp_max = 0;
            int k = 0;
            for (int j = 1; j <= n; j++)
            {
                if (!viewed[j] && dist[j] > tmp_max)
                {
                    tmp_max = dist[j];
                    k = j;
                }
            }
            viewed[k] = 1;
            // update the max flow of not-viewed points that linked to k
            for (int j = 1; j <= n; j++)
            {
                if (!viewed[j] && graph[k][j])
                {
                    int delta = min(graph[k][j], dist[k]);
                    if (delta > dist[j])
                    {
                        dist[j] = delta;
                        pre[j] = k;
                    }
                }
            }
        }// end for of i
    }
    
    
};

int main()
{
    int graph[maxn][maxn] = { 0 };
    int n, m, s, t;
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        graph[u][v] = graph[v][u] = w;
    }
    
    Dijkstra_maxflow dijkstra(n, m, s, t, graph);
    dijkstra.work();
    cout << dijkstra.dist[t] << endl;
    
    return 0;
}
Last modification:May 11th, 2020 at 09:20 am
如果觉得我的文章对你有用,请随意赞赏