「Bzoj 2200」「Usaco2011 Jan」道路和航线(最短路+DAG图拓扑序转移)

BZOJ 2200
题意:无向图中求$S$出发到每个点的最短路。并且有一些单向边,如果有一条单向边可以从$A_i$到$B_i$,那么保证不可能通过一些双向边和单向边从$B_i$回到$A_i$

显然最短路模板,但是有负权图并且卡 SPFA。
所以我们利用

如果有一条单向边可以从$A_i$到$B_i$,那么保证不可能通过一些双向边和单向边从$B_i$回到$A_i$

发现这些有向边将无向图分成了几个联通块,即不加入这些有向边,原图为几个连通块。
所以我们将联通块缩点,然后就成了 DAG 上的最短路,然后拓扑序来求即可。

具体实现看代码。

知识点:
1、负权图转移要注意判 != INF

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 25000 + 5;
const LL INF = 4223372036854775808ll;
struct edge {
int u, v, w;
}ed[200000 + 5];
struct data {
int u;
LL dis;
bool operator < (const data &rhs) const {return dis > rhs.dis;}
};
int n, m, p, s, f[MAXN], en, ino[MAXN], vis[MAXN]; // f[节点编号], ino[联通块代表编号], vis[节点编号]
vector<int > G[MAXN], whw[MAXN]; // G[节点编号][ith]=边编号
LL dis[MAXN]; //dis[节点编号]
queue<int > qq; // qq<联通块代表编号>
int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);} // find(节点编号)
void ins(int x, int y, int v) {ed[++en] = (edge){x, y, v}, G[x].push_back(en);} // ins(节点编号, 节点编号, 值)
priority_queue<data > q; // q<信息>[联通块代表编号]
void dij(int nx) {
for (int i = 0; i < (int)whw[nx].size(); ++i) q.push((data){whw[nx][i], dis[whw[nx][i]]});
while (!q.empty()) {
data p = q.top(); q.pop();
if (vis[p.u]) continue ; vis[p.u] = 1;
for (int i = 0; i < (int)G[p.u].size(); ++i) {
edge &e = ed[G[p.u][i]];
if (dis[e.v] > dis[p.u] + e.w && dis[p.u] != INF) { // 负权图注意判 != INF
dis[e.v] = dis[p.u] + e.w;
if (find(e.v) == nx) q.push((data){e.v, dis[e.v]});
}
}
}
for (int i = 0; i < (int)whw[nx].size(); ++i) { // 把边删完
int u = whw[nx][i];
for (int j = 0; j < (int)G[u].size(); ++j) {
int v = ed[G[u][j]].v;
if (find(v) == nx) continue ;
--ino[find(v)];
if (ino[find(v)] == 0) qq.push(find(v));
}
}
}
void clean() {
ms(vis, 0), ms(ino, 0), en = 0;
}
int solve() {
clean();
scanf("%d%d%d%d", &n, &m, &p, &s);
for (int i = 0; i <= n; ++i) f[i] = i;
for (int x, y, v, i = 1; i <= m; ++i) {
scanf("%d%d%d", &x, &y, &v);
ins(x, y, v), ins(y, x, v);
int hx = find(x), hy = find(y);
if (hx != hy) f[hx] = hy;
}
for (int x, y, v, i = 1; i <= p; ++i) {
scanf("%d%d%d", &x, &y, &v), ins(x, y, v);
}
for (int i = 2 * m + 1; i <= 2 * m + p; ++i) {
int hx = find(ed[i].u), hy = find(ed[i].v);
if (hx != hy) ++ino[hy];
}
for (int i = 1; i <= n; ++i) whw[find(i)].push_back(i);
for (int i = 1; i <= n; ++i) dis[i] = INF;
dis[s] = 0ll;
for (int i = 1; i <= n; ++i) if (find(i) == i && ino[i] == 0) qq.push(i);
while (!qq.empty()) {
int p = qq.front(); qq.pop();
dij(p);
}
for (int i = 1; i <= n; ++i) if (dis[i] == INF) printf("NO PATH\n"); else printf("%lld\n", dis[i]);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
//21:17 - :34 - 20:48 - 20:48 - 20:56
//Start - Finish - Static - Sample - AC
/*
4 0 4 3
1 3 5
1 4 4
3 4 6
4 2 6
*/

------ 本文结束 ------