题目链接

BZOJ2200

题目描述

lyd 算法竞赛进阶指南
详见原题描述

思路要点

负权边只存在单向边,且不存在负权环,而且所有的双向边可以构成若干个联通块。

考虑用一种拓扑排序套最短路算法的做法来实现此题。

先缩点,然后按照单向边建立新图,按照拓扑排序的做法来一一遍历新图。

将遍历到的联通块内的所有节点都塞进一个堆中,然后用 $Dijkstrea$ 的做法更新其他的节点。

如果遍历到的节点不是同一个联通块中,其入度$--$,如果变为$0$就塞入队列。

时间复杂度 $O(nlogn)$。

代码

/*
 * @Author: chhokmah 
 * @Date: 2020-03-23 09:09:57 
 * @Last Modified by:   chhokmah 
 * @Last Modified time: 2020-03-23 09:09:57 
 */
#include <bits/stdc++.h>

using namespace std;

const int N = 3e4 + 5;

struct State {
  int u, d;

  bool operator<(const State& rhs) const {
    return d > rhs.d;
  }
};

vector< pair<int, int> > g[N];
int n, m1, m2, s, scc;
int bel[N], idg[N], dis[N];
bool vis[N];
vector<int> id[N];

void dfs(int u) {
  bel[u] = scc;
  id[scc].emplace_back(u);
  for (auto v : g[u]) {
    if (!bel[v.first]) {
      dfs(v.first);
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cin >> n >> m1 >> m2 >> s;
  for (int i = 1; i <= m1; i++) {
    int u, v, w; 
    cin >> u >> v >> w;
    g[u].emplace_back(make_pair(v, w));
    g[v].emplace_back(make_pair(u, w));
  }
  for (int i = 1; i <= n; i++) {
    if (!bel[i]) {
      ++scc;
      dfs(i);
    }
  }
  for (int i = 1; i <= m2; i++) {
    int u, v, w; 
    cin >> u >> v >> w;
    idg[bel[v]]++;
    g[u].emplace_back(make_pair(v, w));
  }
  memset(vis, 0, sizeof vis);
  queue<int> q;
  for (int i = 1; i <= scc; i++) {
    if (idg[i] == 0) {
      q.push(i);
    }
  }
  priority_queue<State> pq;
  memset(dis, 0x3f, sizeof dis);
  dis[s] = 0;
  while (!q.empty()) {
    int cur = q.front(); 
    q.pop();
    for (auto el : id[cur]) {
      pq.push((State){el, dis[el]});
    }
    while (!pq.empty()) {
      int u = pq.top().u;
      pq.pop();
      if (vis[u]) {
        continue;
      }
      vis[u] = 1; 
      for (auto it : g[u]) {
        int v = it.first, w = it.second;
        if (bel[v] != bel[u]) {
          if (dis[v] > dis[u] + w) {
            dis[v] = dis[u] + w; 
          }
          idg[bel[v]]--;
          if (idg[bel[v]] == 0) {
            q.push(bel[v]);
          }
        } else {
          if (dis[v] > dis[u] + w) {
            dis[v] = dis[u] + w; 
            pq.push((State){v, dis[v]});
          }
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (dis[i] >= 100000000) {
      cout << "NO PATH" << '\n';
    } else {
      cout << dis[i] << '\n';
    }
  }
  return 0;
}

后言

  • 像这道题,因为存在负权单项边和正权双向边两种边,可以提示选手分成两个阶段思考问题。
  • 思想不要局限于单一的最短路求法,拓扑排序对于DAG的最短路求法有奇效,也可以向这个方向思考。
最后修改:2020 年 03 月 23 日 09 : 14 AM
如果觉得我的文章对你有用,请随意赞赏