【Floyd】ABC243 E - Edge Deletion

我就是我 2024-03-23 11:25 51阅读 0赞

[E - Edge Deletion (atcoder.jp)][E - Edge Deletion _atcoder.jp]

题意：

有多少条边可以删除后不影响任意两点之间的最短距离和图的连通性。

![1d68bf0fcc0e4f7e9bd18a98f912179f.png][]

思路：

考虑特殊性质

这道题，有两个切入点：数据范围300和不影响最短路这两个条件

首先300明示了我们用Floyd

然后去掉一条边之后两点之间最短路不变，说明存在另一结点k使得k能松弛i和j，因此在跑Floyd的时候可以标记一下两点之间的边是否存在第三点来松弛，如果存在就说明该边是可删的

Code：

#include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=3e2+10;
    const int mxe=1e6+10;
    const int Inf=1e18;
    struct ty{
        int to,next,w;
    }edge[mxe<<2];
    
    int n,m,u,v,w,tot=0;
    int head[mxn],dis[mxn][mxn],e[mxn][mxn],vis[mxn][mxn];
    void add(int u,int v,int w){
        edge[tot].w=w;
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void G_init(){
        tot=0;
        for(int i=0;i<=n;i++){
            head[i]=-1;
        }
    }
    void solve(){
        cin>>n>>m;
        G_init();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==j) continue;
                dis[i][j]=1e18;
            }
        }
        for(int i=1;i<=m;i++){
            cin>>u>>v>>w;
            dis[u][v]=dis[v][u]=min(dis[u][v],w);
            e[u][v]=w;
        }
        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    if(i==j||i==k||j==k) continue;
                    if(dis[i][j]>=dis[i][k]+dis[k][j]){
                        dis[i][j]=dis[i][k]+dis[k][j];
                        vis[i][j]=1;
                    }
                }
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(vis[i][j]==1&&e[i][j]!=0&&e[i][j]>=dis[i][j]) ans++;
            }
        }
        cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[E - Edge Deletion _atcoder.jp]: https://atcoder.jp/contests/abc243/tasks/abc243_e
[1d68bf0fcc0e4f7e9bd18a98f912179f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/f1633001ac3c4a6d8df38c03c27ed4ac.png