andyli

题解 UVA1416 【Warfare And Logistics】
如果用$floyd$算法计算$c$,每尝试着删除一条边都要重新计算一次,时间复杂度为$O(n^3m)$,很难承受。...
扫描右侧二维码阅读全文
24
2019/06

题解 UVA1416 【Warfare And Logistics】

如果用$floyd$算法计算$c$,每尝试着删除一条边都要重新计算一次,时间复杂度为$O(n^3m)$,很难承受。如果用$n$次$Dijkstra$计算单源最短路,时间复杂度为$O(nm^2\log n)$。虽然看上去比$O(n^3m)$略好,但由于$floyd$算法的常数很小,实际运行时间差不多。这时候,最短路树派上用场了。因为在源点确定的情况下,只要最短路树不被破坏,起点到所有点的距离都不会发生改变。换句话说,只有删除最短路树上的$n-1$条边,最短路树才需要重新计算。这样,对于每个源点,最短只需要求n次而不是$m$次单源最短路,时间复杂度降为$O(n^2m\log n)$,可以承受。另外,本题有一个不容易发现的“陷阱”:如果有重边,删除一条边时2,应该用第二短的边代替。
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000, maxn = 105;

struct Edge
{
    int u, v, w;
    Edge(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {}
};

struct HeapNode
{
    int d, u;
    HeapNode(int d = 0, int u = 0) : d(d), u(u) {}
    bool operator<(const HeapNode& rhs) const { return d > rhs.d; }
};

struct Dijkstra
{
    int n, m;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool vis[maxn];  // 是否已永久标号
    int d[maxn];     // s到各个点的距离
    int p[maxn];     // 最短路中的上一条弧

    void init(int n)
    {
        this->n = n;
        for (int i = 0; i < n; i++)
            G[i].clear();
        edges.clear();
    }

    void AddEdge(int u, int v, int w)
    {
        edges.emplace_back(u, v, w);
        m = edges.size();
        G[u].push_back(m - 1);
    }
    void dijkstra(int s)
    {
        priority_queue<HeapNode> q;
        for (int i = 0; i < n; i++)
            d[i] = INF;
        d[s] = 0;
        memset(vis, 0, sizeof(vis));
        q.emplace(0, s);
        while (!q.empty())
        {
            HeapNode x = q.top();
            q.pop();
            int u = x.u;
            if (vis[u])
                continue;
            vis[u] = true;
            for (size_t i = 0; i < G[u].size(); i++)
            {
                Edge& e = edges[G[u][i]];
                if (e.w > 0 && d[e.v] > d[u] + e.w)
                {  // 此处和模板不同,忽略了dist=-1的边。此为删除标记。根据题意和dijkstra算法的前提,正常的边dist>0
                    d[e.v] = d[u] + e.w;
                    p[e.v] = G[u][i];
                    q.emplace(d[e.v], e.v);
                }
            }
        }
    }
};

Dijkstra solver;
int n, m, L;
vector<int> gr[maxn][maxn];  // 两点之间的原始边权
bool used[maxn][maxn][maxn];  // used[src][a][b]表示源点为src的最短路树是否包含边a->b
int idx[maxn][maxn];  // idx[u][v]为边u->v在Dijkstra求解器中的编号
int sum_single[maxn];  // sum_single[src]表示源点为src的最短路树的所有d之和

int compute_c()
{
    int ans = 0;
    memset(used, 0, sizeof(used));
    for (int u = 0; u < n; u++)
    {
        solver.dijkstra(u);
        sum_single[u] = 0;
        for (int i = 0; i < n; i++)
        {
            if (i != u)
            {
                int fa = solver.edges[solver.p[i]].u;
                used[u][fa][i] = used[u][i][fa] = true;
            }
            sum_single[u] += (solver.d[i] == INF ? L : solver.d[i]);
        }
        ans += sum_single[u];
    }
    return ans;
}

int compute_newc(int a, int b)
{
    int ans = 0;
    for (int u = 0; u < n; u++)
        if (!used[u][a][b])
            ans += sum_single[u];
        else
        {
            solver.dijkstra(u);
            for (int i = 0; i < n; i++)
                ans += (solver.d[i] == INF ? L : solver.d[i]);
        }
    return ans;
}

int main()
{
    while (~scanf("%d%d%d", &n, &m, &L))
    {
        solver.init(n);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                gr[i][j].clear();
        for (int i = 0; i < m; i++)
        {
            int a, b, s;
            scanf("%d%d%d", &a, &b, &s);
            a--, b--;
            gr[a][b].push_back(s), gr[b][a].push_back(s);
        }
        // 构造网络
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (!gr[i][j].empty())
                {
                    sort(gr[i][j].begin(), gr[i][j].end());
                    solver.AddEdge(i, j, gr[i][j][0]);
                    idx[i][j] = solver.m - 1;
                    solver.AddEdge(j, i, gr[i][j][0]);
                    idx[j][i] = solver.m - 1;
                }

        int c = compute_c(), c2 = -1;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (!gr[i][j].empty())
                {
                    int &e1 = solver.edges[idx[i][j]].w,
                        &e2 = solver.edges[idx[j][i]].w;
                    if (gr[i][j].size() == 1)
                        e1 = e2 = -1;
                    else
                        e1 = e2 = gr[i][j][1];  // 第二短边
                    c2 = max(c2, compute_newc(i, j));
                    e1 = e2 = gr[i][j][0];  // 恢复
                }

        printf("%d %d\n", c, c2);
    }
    return 0;
}
Last modification:June 25th, 2019 at 11:28 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment