UVA1416 Warfare And Logistics（最短路/树）

Warfare And Logistics

The army of United Nations launched a new wave of air strikes on terroristforces. The objective of the mission is to reduce enemy's logistical mobility. Each airstrike will destroy a path and therefore increase the shipping cost of the shortest pathbetween two enemy locations. The maximal damage is always desirable.

Let's assume that there are n enemy locations connected by m bidirectional paths,each with specific shipping cost. Enemy's total shipping cost is given as $\sum_{i=1}^{n}\sum_{j=1}^{n}path(i, j)$. Here path(i, j) is the shortest path between locations i and j. In case i and j are not connected, path(i, j) = L. Each air strike can only destroy one path. The total shipping cost after the strike is noted as c'. In order to maximizedthe damage to the enemy, UN's air force try to find the maximal c' - c.

Input

The first line ofeach input case consists ofthree integers: n, m, and L. $1 < n <= 100,1 <= m <= 1000, 1 <= L <= 10^8$. Each ofthe following m lines contains three integers: a,b, s, indicating length of the path between a and b.

Output

For each case, output the total shipping cost before the air strike and the maximaltotal shipping cost after the strike. Output them in one line separated by a space.

Sample Input

Sample Output

28  38

链接

https://cn.vjudge.net/problem/UVA-1416

题意

给出一个n个点m条边的带权无向图，令c等于每对结点之间的最短路径之和。要求删除一条边后使得新的c值c'最大。不连通两点的最长路视为L。

题解

如果用floyd算法计算c，每尝试着删除一条边都要重新计算一次，时间复杂度为$O(n^3m)$，很难承受。如果用n次Dijkstra计算单源最短路，时间复杂度为$O(nm^2logn)$。虽然看上去比$O(n^3m)$略好，但由于floyd算法的常数很小，实际运行时间差不多。这时候，最短路树派上用场了。因为在源点确定的情况下，只要最短路树不被破坏，起点到所有点的距离都不会发生改变。换句话说，只有删除最短路树上的n-1条边，最短路树才需要重新计算。这样，对于每个源点，最多只需要求n次而不是m次单源最短路，时间复杂度降为$O(n^2mlogn)$，可以承受。注意：如果有重边，删除一条边时，应该用第二短的边代替。
最短路树。用Dijkstra算法可以求出单源最短路树，方法是在发现$d[i]+w(ij)<d[j]$时除了更新d[j]之外还要设置p[i]=j。这样，把p看成是父指针，则所有点形成了一棵树。这样，要从起点出发沿最短路走到任意其他点，只需要顺着树上的边走即可。前面的Dijkstra算法的代码已经求出了p数组。
——小白书P330

还是使用堆优化的dijkstra跑最短路，但是每条边加一个状态记录边的编号，在跑最短路的时候把最短路上的边都记录下来，然后删除这些边重新计算。有一位老哥关于本题的代码写的很好：传送门。

代码

Status	Accepted
Time	200ms
Length	2557

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 110;
const int maxm = 1010;
ll dist[maxn], ans[maxm];
bool vis[maxn];
int pre1[maxn], pre2[maxn];
int n, m, L;

struct Node
{
    int v;
    ll dis;
    Node(int _v, ll _dis): v(_v), dis(_dis) {}
    bool operator < (const Node & r) const
    {
        return dis > r.dis;
    }
};

struct Edge
{
    int to, id, cost;
    Edge(int _to, int _cost, int _id): to(_to), cost(_cost), id(_id) {}
};

vector <Edge> edge[maxn];

void addedge(int u, int v, int w, int id)
{
    edge[u].push_back(Edge(v, w, id));
}

ll dijkstra(int s, int e)
{
    for (int i = 0; i <= n; ++i)
    {
        dist[i] = inf;
        pre1[i] = 0;
        vis[i] = false;
    }
    dist[s] = 0;
    priority_queue <Node> Q;
    Q.push(Node(s, dist[s]));
    while (!Q.empty())
    {
        Node tmp = Q.top();
        Q.pop();
        int u = tmp.v;
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = 0; i < edge[u].size(); ++i)
        {
            int id = edge[u][i].id, v = edge[u][i].to;
            if (id == e)
                continue;
            if (!vis[v] && dist[v] > dist[u] + edge[u][i].cost)
            {
                dist[v] = dist[u] + edge[u][i].cost;
                pre1[v] = id; // 记录边的编号
                Q.push(Node(v, dist[v]));
            }
        }
    }
    ll sum = 0;
    for (int i = 1; i <= n; ++i) // 从s出发的所有最短路
    {
        if (dist[i] == inf)
            sum += L;
        else
            sum += dist[i];
    }
    return sum;
}

void solve()
{
    for (int i = 1; i <= n; ++i)
    {
        ll cost = dijkstra(i, 0);
        for (int j = 0; j <= m; ++j) // 不删边时的最短路和
            ans[j] += cost;
        memcpy(pre2, pre1, sizeof(pre1)); // 将记录的最短路编号复制给pre2数组
        for (int j = 1; j <= n; ++j)
        {
            if (pre2[j]) // 删除边pre2[j]后的最短路之和
                ans[pre2[j]] += ((dijkstra(i, pre2[j])) - cost);
        }
    }
}

int main()
{
    int u, v, w;
    while (scanf("%d%d%d", &n, &m, &L) != EOF)
    {
        for (int i = 0; i <= n; ++i)
            edge[i].clear();
        for (int i = 0; i <= m; ++i)
            ans[i] = 0;
        for (int i = 1; i <= m; ++i) // 边的编号从1开始
        {
            scanf("%d%d%d", &u, &v, &w);
            addedge(u, v, w, i);
            addedge(v, u, w, i);
        }
        solve();
        ll tmp = 0;
        for (int i = 1; i <= m; ++i) // 得到一个最大值
            tmp = max(tmp, ans[i]);
        printf("%lld %lld\n", ans[0], tmp); // ans[0]表示不删边时任意两点的最短路之和
    }
    return 0;
}

The end.
2018-08-23 星期四