本文共 6032 字，大约阅读时间需要 20 分钟。

题意：给一个$n$个点，$m$条有权边的无向图。每个点有一个颜色。多次查询在线查询$xw$，从$x$出发，只能走边权小于等于$w$的边，可以到达的所有点中数量最多的颜色。

思路：最小生成树+dsu on tree+倍增

• 首先把图变成最小生成树，因为边权大的边没用；
• 在kruskal过程中，把边变成点，点权为这条边的边权，并把连接的两边变成其左右儿子，得到一颗叶子节点都是原节点，内部节点都是原边的有根树。而且这颗树的点权从下往上是递增的。
• 此时，问题变成，从点$x$向上找点权小于等于$w$的点$v$。以点$v$为根的子树中数量最多的颜色。这可以使用dsu on tree解决。在每个内部节点$v$都统计子树中最多的颜色$c[v]$。
• 在线查询时，只需要倍增向上找最上面一个点权小于等于$w$的点，再输出这个点的$c[v]$.
  

举例：

原图为 转化为树

#include 
   
    typedef long long ll;#define mp make_pairusing namespace std;using PII = pair
    
     ;const int M = 2e5 + 5;int n, m, tot, mxsz, mxcol;int c[M], f[M], fv[M], val[M], siz[M], big[M], cnt[M], p[M][22], pval[M][22];vector
     
       G[M];pair
      
        edge[M];int findf(int x){
       return x == f[x] ? x : f[x] = findf(f[x]);}void dfsize(int v){
       siz[v] = 1;    for(int u : G[v]){
           p[u][0] = v;        pval[u][0] = val[v];        dfsize(u);        siz[v] += siz[u];    }}void add(int v, int x){
       if(v <= n){
           cnt[c[v]] += x;        if(mxsz < cnt[c[v]] || mxsz == cnt[c[v]] && c[v] < mxcol)            mxsz = cnt[c[v]], mxcol = c[v];    }    for(int u : G[v])        if(!big[u])add(u, x);}void dfs(int v, bool keep){
       int ms = 0, son = 0;    for(int u : G[v])        if(siz[u] > ms)ms = siz[u], son = u;    for(int u : G[v])        if(u != son)dfs(u, 0);    if(son)dfs(son, 1), big[son] = 1;    add(v, 1);    if(val[v])c[v] = mxcol;    big[son] = 0;    if(!keep){
           add(v, -1);        mxsz = mxcol = 0;    }}int query(int v, int x){
       for(int i = 20; i >= 0; --i){
           if(!p[v][i] || pval[v][i] > x)continue;        v = p[v][i];    }    return c[v];}int main() {
       ios::sync_with_stdio(false);    cin.tie(0);    int T = 1, cas = 1;    cin >> T;    while(T--){
           memset(p, 0, sizeof(p));        memset(val, 0, sizeof(val));        for(int i = 1; i < M; ++i)            G[i].clear();        cin >> n >> m;        tot = n;        for(int i = 1; i <= n; ++i){
               f[i] = i;            fv[i] = i;            cin >> c[i];        }        for(int x, y, w, i = 1; i <= m; ++i){
               cin >> x >> y >> w;            edge[i] = mp(w, mp(x, y));        }        sort(edge + 1, edge + m + 1);        for(int cnt = 1, x, y, w, i = 1; i <= m && cnt < n; ++i){
               x = edge[i].second.first, y = edge[i].second.second, w = edge[i].first;            if(findf(x) == findf(y))continue;            ++cnt;            val[++tot] = w;            G[tot].push_back(fv[findf(x)]);            G[tot].push_back(fv[findf(y)]);            f[findf(x)] = findf(y);            fv[findf(y)] = tot;        }        dfsize(tot);        for(int i = 1; i <= 20; ++i){
               for(int v = 1; v <= tot; ++v){
                   p[v][i] = p[p[v][i-1]][i-1];                pval[v][i] = pval[p[v][i-1]][i-1];            }        }        dfs(tot, 0);        //cout << p[8][0] << " == " << pval[8][0] << endl;        cout << "Case #" << cas++ << ":" << endl;        int last = 0, q, x, w;        cin >> q;        while(q--){
               cin >> x >> w;            x = x ^ last;            w = w ^ last;            cout << (last = query(x, w)) << endl;        }    }}
      
     
    
   

题意：给定一个$n$个点、$m$条边的带权无向图，其中有$s$个点是加油站。每辆车都有一个油量上限$b$，即每次行走距离不能超过$b$，但在加油站可以补满。

$q$次询问，每次给出$x,y,b$，表示出发点是x，终点是y，油量上限为b，且保证x点和y点都是加油站，请回答能否从x走到y。 思路：和上一题类似，都是从一个点出发，限定边权，找信息。但是，这题的变化是，多了很多不是加油站的点。问题转化为怎么把非加油站的点连的边，变成加油站和加油站之间的边。

我们记from[i]表示离$i$最近的关键点，仔细考虑一下，A->B的最短路径上，一定是前一半的from[i]为A，然后走过某条路以后，后一半的from[i]为B。为什么呢？我们不妨设中间出现了一个点x的from[x]=C，那么我们大可以从A走到C，加满油，再从C走到B，这样一定不会差！所以AB之间是否有边就看是否满足这样的条件了……

下图中，5 -> 6的最短距离为11，但是由于form[4] = 1, from[5] = 5,form[6]=6,所以连接了1->5和1->6，没有直接连接5->6，但是这里5->1加满油后，再1->6这样一定不会差，因为5->1的距离小于5->6的距离才会有form[4] = 1。这样会更优！

所以，对于每条边$(u,v,w)$，若$form[u]\ne form[v]$则添加边$(form[u],form[v],dis[u]+w+dis[v])$ 最后，把查询安油箱容量从小到大排序。kruskal过程中，判断是否能通过，省去倍增过程。

#include 
   
    typedef long long ll;#define mp make_pairusing namespace std;using PII = pair
    
     ;using LL = long long;const int M = 2e5 + 5;int n, s, m;int c[M], dis[M], vis[M], pre[M], gas[M], ans[M], f[M];vector
     
       G[M];vector< pair
      
        > edge, edge2;vector< pair< int, pair
       
         > > que;int findf(int x){
       return x == f[x] ? x : f[x] = findf(f[x]);}void dijkstra(){
       memset(dis, 0x7f, sizeof(dis));    priority_queue
        
         , greater
         
           > Q; for(int i = 1; i <= s; ++i){ Q.emplace(0, c[i]); dis[c[i]] = 0; pre[c[i]] = c[i]; } while(!Q.empty()){ int x = Q.top().second; Q.pop(); if(vis[x])continue; vis[x] = true; for(PII p : G[x]) if(dis[x] + p.first < dis[p.second]) dis[p.second] = dis[x] + p.first, pre[p.second] = pre[x], Q.emplace(dis[p.second], p.second); }}int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> s >> m; for(int i = 1; i <= s; ++i){ cin >> c[i]; gas[c[i]] = 1; } for(int x, y, z, i = 0; i < m; ++i){ cin >> x >> y >> z; G[x].emplace_back(z, y); G[y].emplace_back(z, x); if(gas[x] && gas[y])edge2.emplace_back(z, mp(x, y)); else edge.emplace_back(z, mp(x, y)); } int q; cin >> q; for(int x, y, z, i = 1; i <= q; ++i){ cin >> x >> y >> z; que.emplace_back(z, mp(i, mp(x, y))); } sort(que.begin(), que.end()); dijkstra(); for(pair
          
            e : edge){ int x = e.second.first, y = e.second.second, z = e.first; if(pre[x] == pre[y])continue; edge2.emplace_back(dis[x] + z + dis[y], mp(pre[x], pre[y])); } sort(edge2.begin(), edge2.end()); for(int i = 1; i <= n; ++i) f[i] = i; int cnt = 0; for(auto c : que){ while(cnt < edge2.size() && edge2[cnt].first <= c.first){ int x = findf(edge2[cnt].second.first), y = findf(edge2[cnt].second.second); if(x != y)f[x] = y; ++cnt; } if(findf(c.second.second.first) == findf(c.second.second.second))ans[c.second.first] = 1; else ans[c.second.first] = 0; } for(int i = 1; i <= q; ++i){ cout << (ans[i] ? "TAK" : "NIE") << endl; }}
          
         
        
       
      
     
    
   

转载地址：http://jwuzi.baihongyu.com/