题意:
给定无重边无自环的带正权无向连通图,问最多删除几条边能保持所有点对的最短距离不变
\(n\le 300\)
思路:
删除边 \(u\overset{w}{-}v\) 当且仅当原图中存在其它路径的长度小于等于 \(w\),即存在中间点 \(k\),使得 \(d(u,k)+d(k,v)\le w\)
因为每次都在原图中找其他路径,所以(相比在删除若干边后的新图上找)找到的可能性是最大的。这样会不会删太多了?答案是不会,只需证明这样得到的子图符合题意:
考虑原图中 \(u\) 到 \(v\) 的最短路径中边数最多的那条,记为 \(path\)。若 \(path\) 仅有一条边则 \(u\) 到 \(v\) 的距离没变,符合题意;若 \(path\) 不止一条边则把 \(path\) 拆成两部分,由归纳法可以证明符合题意
可以用 floyd 实现
const int N = 310;
int n, m, ans;
bool g[N][N]; //还有没有此边
ll d[N][N];
void sol() {
memset(d, 0x3f, sizeof d);
cin >> n >> m;
while(m--) {
int x, y, z; cin >> x >> y >> z;
d[x][y] = d[y][x] = z;
g[x][y] = true;
}
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(d[i][j] >= d[i][k] + d[k][j])
d[i][j] = d[i][k] + d[k][j],
ans += g[i][j], g[i][j] = 0;
cout << ans;
}
标签:原图,题意,int,abc243,Edge,Deletion,ans,path
From: https://www.cnblogs.com/wushansinger/p/17052935.html