BZOJ 1576: [Usaco2009 Jan]安全路经Travel

先构出最短路径树(题目说唯一)
对于一个非树边(u,v) 一定使树构成一个环
并且使环上的点(除了lca(u,v))都有了一个次短路
对于点i 这个所谓次短路的长度就是dist[u]+dist[v]+value[u,v]-dist[i]
可以发现次短路大小长度跟u,v有关 跟i无关
所以对于一个非树边(u,v)设它的权值为dist[u]+dist[v]+value[u,v]
把这个权值按从小到大排序 每次把环上没被赋值过的点赋上值
快速实现上面那个 可以用并查集(不用多说了吧=v=)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;
 
const int maxn = 100005;
 
struct line
{
    int to, next, v;
}li[maxn * 10];
 
struct wtf
{
    int v, cost;
    wtf(int a, int b) : v(a), cost(b) {}
};
 
struct hh
{
    int u, v, va;
}t[maxn * 5];
 
int be[maxn], dist[maxn], fa[maxn], f[maxn], d[maxn], tot, ans[maxn], l, n, m, b[maxn];
priority_queue<wtf> q;
 
bool operator<(wtf a, wtf b)
{
    return a.cost > b.cost;
}
 
bool cmp(hh a, hh b)
{
    return a.va < b.va;
}
 
void makeline(int fr, int to, int v)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
    li[l].v = v;
}
 
int getfa(int now)
{
    return (!f[now]) ? now : f[now] = getfa(f[now]);
}
 
void re_ans(int u, int v, int va)
{
    int lastu = -1, lastv = -1;
    while (getfa(u) != getfa(v))
    {
        if (d[getfa(u)] < d[getfa(v)]) swap(u, v), swap(lastu, lastv);
        if (ans[u] == -1)
        {
            ans[u] = va - dist[u];
            if (lastu != -1)
                f[lastu] = u;
        }
        else
            if (lastu != -1)
                f[lastu] = getfa(u);
        lastu = getfa(u);
        u = fa[lastu];
    }
}
 
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i)
    {
        int fr, to, v;
        scanf("%d%d%d", &fr, &to, &v);
        makeline(fr, to, v);
        makeline(to, fr, v);
    }
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    d[1] = 1;
    q.push(wtf(1, 0));
    while (!q.empty())
    {
        while (!q.empty() && b[q.top().v]) q.pop();
        if (q.empty()) break;
        int now = q.top().v;
        b[now] = 1;
        for (int i = be[now]; i; i = li[i].next)
        {
            int to = li[i].to;
            if (b[to] || dist[to] <= dist[now] + li[i].v) continue;
            fa[to] = now;
            d[to] = d[now] + 1;
            dist[to] = dist[now] + li[i].v;
            q.push(wtf(to, dist[to]));
        }
    }/*
    for (int i = 1; i <= n; ++i)
        printf("%d\n", dist[i]);
    printf("\n\n");*/

    for (int i = 1; i <= n; ++i)
        for (int j = be[i]; j; j = li[j].next)
        {
            int to = li[j].to;
            if (to >= i || fa[to] == i || fa[i] == to) continue;
            t[tot].u = i, t[tot].v = to, t[tot].va = dist[i] + dist[to] + li[j].v;
            ++tot;
        }
    memset(ans, -1, sizeof(ans));
    sort(t, t + tot, cmp);
    for (int i = 0; i < tot; ++i)
        re_ans(t[i].u, t[i].v, t[i].va);
    for (int i = 2; i <= n; ++i)
        printf("%d\n", ans[i]);
}

BZOJ 1576: [Usaco2009 Jan]安全路经Travel》上有3条评论

发表评论