Description

路由是指通过计算机网络把信息从源地址传输到目的地址的活动, 也是计算机网络设计中的重点和难点. 网络中实现路由转发的硬件设备称为路由器. 为了使数据包最快的到达目的地, 路由器需要选择最优的路径转发数据包. 例如在常用的路由算法 OSPF (开放式最短路径优 先) 中, 路由器会使用经典的 Dijkstra 算法计算最短路径, 然后尽量沿最短路径转发数据包. 现在, 若已知一个计算机网络中各路由器间的连接情况, 以及各个路由器的最大吞吐量 (即每秒能转发的数据包数量), 假设所有数据包一定沿最短路径转发, 试计算从路由器 1 到路由器 n 的网络的最大吞吐量. 计算中忽略转发及传输的时间开销, 不考虑链路的带宽限制, 即认 为数据包可以瞬间通过网络. 路由器 1 到路由器 n 作为起点和终点, 自身的吞吐量不用考虑, 网络上也不存在将 1 和 n 直接相连的链路.

Input

输入文件第一行包含两个空格分开的正整数 n 和 m, 分别表示路由器数量和链路的数量. 网络 中的路由器使用 1 到 n 编号. 接下来 m 行, 每行包含三个空格分开的正整数 a、b 和 d, 表示从路 由器 a 到路由器 b 存在一条距离为 d 的双向链路. 接下来 n 行, 每行包含一个正整数 c, 分别给出每一个路由器的吞吐量.

Output

输出一个整数, 为题目所求吞吐量.

Sample Input

7 10
1 2 2
1 5 2
2 4 1
2 3 3
3 7 1
4 5 4
4 3 1
4 6 1
5 6 2
6 7 1
1
100
20
50
20
60
1

Sample Output

70

Data Range

对于 100% 的数据,\(n \leq 500, m \leq 100000, d, c \leq 10^9\)

Solution

就是跑一遍最短路, 然后再跑一遍网络流.

求出最短路后, 由于我们在网络流建图时需要加入所有最短路, 所以我们还需要反向跑一遍 BFS 或 DFS 或者直接检测所有加入的边, 这样能够保证所有最短路都加进来.

另一方面, 考虑到每一个点有一个流量限制, 我们需要将每一个点拆成两个, 然后强行要求 需要通过中间的那个流量边以限制流量.

如此一来, 就有了网络流的建图方式. 注意 SPFA 跑的速度实质上要比堆优化 Dijkstra 要快差不多 10% (最短路).

其次还有各种 RE (内存需要多开一倍, 不知道为什么), WA (没删掉调试信息), 双向 建边 Dinic 死循环爆栈等等.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 1010, maxm = 400100;
const lli infinit = 100000000000000;

class ShortestPath
{
public:
    struct edge
    {
        int u, v, len;
        edge *next;
    };
    edge *edges[maxn], epool[maxm];
    int n, s, ecnt;
    lli dist[maxn];
    bool inque[maxn];
    void add_edge(int u, int v, int len)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->len = len;
        p->next = edges[u]; edges[u] = p;
        q->u = v; q->v = u; q->len = len;
        q->next = edges[v]; edges[v] = q;
        return ;
    }
    void eval(void)
    {
        queue<int> que;
        for (int i = 1; i <= n; i++)
            inque[i] = false, dist[i] = infinit;
        que.push(s);
        inque[s] = true;
        dist[s] = 0;
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (dist[p] + ep->len < dist[ep->v]) {
                    dist[ep->v] = dist[p] + ep->len;
                    if (!inque[ep->v]) {
                        que.push(ep->v);
                        inque[ep->v] = true;
                    }
                }
            inque[p] = false;
        }
        // for (int i = 1; i <= n; i++)
        //     cout << dist[i] << ' ';
        // cout << endl;
        return ;
    }
} sp;

class MaxFlow
{
public:
    struct edge
    {
        int u, v;
        lli flow;
        edge *rev, *next;
    };
    edge *edges[maxn], epool[maxm];
    int n, s, t, ecnt;
    int depth[maxn];
    void add_edge(int u, int v, lli flow)
    {
        // printf("add edge %d %d %lld\n", u, v, flow);
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = 0;
        q->next = edges[v]; edges[v] = q; q->rev = p;
        return ;
    }
    bool make_level(void)
    {
        queue<int> que;
        memset(depth, 0, sizeof(depth));
        que.push(s);
        depth[s] = 1;
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (!depth[ep->v] && ep->flow > 0) {
                    depth[ep->v] = depth[p] + 1;
                    que.push(ep->v);
                }
            if (depth[t] > 0)
                return true;
        }
        return false;
    }
    lli find(int p, lli mn)
    {
        if (p == t)
            return mn;
        lli sum = 0, tmp = 0;
        for (edge *ep = edges[p]; ep && mn > 0; ep = ep->next)
            if (depth[ep->v] == depth[p] + 1 && ep->flow) {
                tmp = find(ep->v, min(mn, ep->flow));
                if (tmp > 0) {
                    ep->flow -= tmp;
                    ep->rev->flow += tmp;
                    sum += tmp;
                    mn -= tmp;
                }
            }
        return sum;
    }
    lli eval(void)
    {
        lli sum = 0, tmp = 0;
        while (make_level()) {
            tmp = find(s, infinit);
            if (tmp <= 0)
                break;
            sum += tmp;
        }
        return sum;
    }
} mf;

int n, m;
lli data[maxn];

// Copies data from ShortestPath to MaxFlow and further process the information.
void copy_data(void)
{
    // Creating real edges, with no connectivity.
    for (int i = 1; i <= sp.ecnt; i++) {
        ShortestPath::edge *ep = &sp.epool[i];
        if (sp.dist[ep->u] + ep->len == sp.dist[ep->v])
            mf.add_edge(n + ep->u, ep->v, infinit);
    }
    // Delimiting flow between the auxillary and the actual graph
    for (int i = 1; i <= n; i++) {
        if (i == 1 || i == n)
            mf.add_edge(i, n + i, infinit);
        else
            mf.add_edge(i, n + i, data[i]);
    }
    // Setting parameters
    mf.s = 1;
    mf.t = mf.n = 2 * n;
    return ;
}

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    for (int i = 1, a, b, c; i <= m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        sp.add_edge(a, b, c);
    }
    for (int i = 1; i <= n; i++)
        scanf("%d", &data[i]);
    // Calculating shortest path.
    sp.n = n; sp.s = 1;
    sp.eval();
    // Migrating data.
    copy_data();
    // Running maxflow.
    lli res = mf.eval();
    // Retrieve the result.
    printf("%lld\n", res);
    return 0;
}