题解：AT_abc243_e [ABC243E] Edge Deletion

· · 题解

ABC243E Edge Deletion

题意：

一张简单联通带权无向图，询问最多删多少边能保证任意两点间最短路长度不变。N\le 300。

解法：

看到数据范围就猜到是 Floyd 了，问题在如何用 Floyd 解。

一个显而易见的结论：一条边可以被删除仅当有另外一条联通两点的路径长度小于等于该边。因为另外一条路径可以作为这两点的最短路，经过这两点的最短路也可以走这条更短的路径，所以这条边没有必要存在。

然后改一下 Floyd 板子就可以了。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=305,inf=1e16;
ll n,m;
ll e[N][N],dis[N][N];
bool vis[N][N];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    //初始化Floyd
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dis[i][j]=inf;
    for(int i=1;i<=n;i++)dis[i][i]=0;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        dis[u][v]=dis[v][u]=e[u][v]=e[v][u]=w;
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            if(i==k)continue;
            for(int j=1;j<=n;j++){
                if(j==k || i==j)continue;
                if(dis[i][k]+dis[k][j]<=dis[i][j] && e[i][j])vis[i][j]=vis[j][i]=1;//如果存在i-j的边且这条边不是唯一最优，标记其可以删除。
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(vis[i][j])ans++;
    cout<<ans;
    return 0;
}