P1841
给定一张图，求有多少点满足，删除该点之后存在两点的最短路被改变。该两点均不为被删除的点。
\(n \le 300, m \le n(n-1)/2\)
对于一个起点 \(s\)，建出最短路图。因此 \(c>0\)，所以必然是 DAG。现在问题转化成：在 DAG 上每次考虑删除一个点，是否会出现 \(s\) 无法到一个原来能够到达的点？
这里我当时出的问题很乐。枚举起点是 \(O(n)\)，枚举删除的点也是 \(O(n)\) 的。当时我每次都跑一个 dfs，以为自己 \(O(n^2(n+m))\)。但是 \(m\) 是 \(n^2\) 级别的。
最短路图满足起点到任意一个点均有通路。删除一个点 \(u\) 无法到达别的点的充要条件是存在边 \((u, v)\)，使得 \(v\) 的入度为 1。这是容易证明的：因为 \(v\) 入度为 \(1\)，所以 \(s\) 到 \(v\) 只有一条通路。删除 \(u\) 就会消除这条通路。从而到不了。
画画图是容易得到结论的
#include <bits/stdc++.h>
using namespace std;
const int N = 200, inf = 2e6;
struct node {
int to, val;
node(int T, int V) {
to = T, val = V;
}
};
vector <node> gra[N + 10];
bool br[N + 10], vis[N + 10];
int dis[N + 10], n, m, deg[N + 10];
void dij(int s) {
for(int i = 1; i <= n; i++)
dis[i] = inf, vis[i] = 0;
dis[s] = 0;
for(int i = 1; i <= n; i++) {
int x = 0;
for(int j = 1; j <= n; j++)
if(!vis[j] && ((x == 0) || (dis[j] < dis[x])))
x = j;
vis[x] = 1;
for(int j = 0; j < gra[x].size(); j++) {
int v = gra[x][j].to, w = gra[x][j].val;
if(dis[v] > dis[x] + w)
dis[v] = dis[x] + w;
}
}
for(int i = 1; i <= n; i++)
if(dis[i] >= inf) vis[i] = 0;
}
void work(int s) {
dij(s);
for(int u = 1; u <= n; u++) deg[u] = 0;
for(int u = 1; u <= n; u++) {
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i].to, w = gra[u][i].val;
if(dis[v] == dis[u] + w) deg[v]++;
}
}
for(int u = 1; u <= n; u++) {
if(br[u]) continue;
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i].to, w = gra[u][i].val;
if(dis[v] != dis[u] + w) continue;
if(deg[v] == 1 && u != s) br[u] = 1;
}
}
}
int main() {
cin >> n >> m;
for(int i = 1, x, y, z; i <= m; i++) {
cin >> x >> y >> z;
gra[x].push_back(node(y, z));
gra[y].push_back(node(x, z));
}
for(int i = 1; i <= n; i++)
work(i);
int cnt = 0;
for(int i = 1; i <= n; i++)
if(br[i]) cout << i << ' ', cnt++;
if(!cnt) {
cout << "No important cities." << endl;
return 0;
}
}
总结
- 最短路图在结构上有一些可能较为特别的性质
- 只有起点入度为 \(0\)。
- 起点到每个点均有通路。
- 一定要注意稠密图中 \(m\) 是 \(n^2\) 级别的。