E – Edge Deletion

题目描述：

n个点，m条边，问最多能删掉多少边，使的终图保持和原图一样的连通性，且任意两个点的最短路之间的距离不变

思路：

n很小，可以先跑floyed，求出多源最短路

判断一条边a b c能不能删的条件可以分成两种：直接计算、间接计算

• 直接计算：dis[a][b] < c || num[a][b] > 1，也就是a到b的最短路长度小于c,或者a到b的最短路的数量大于1
• 间接计算：对于每对i j，我们可以枚举中间节点k,如果dis[i][j]=dis[i][k] + dis[k][j]，则表明这存在一条边i,j是在最短路上的，也就是不可以删掉的，统计出这种边，用所有的边的数量减去即可

//直接计算
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
int tr[505][505];
int num[505][505];
struct ran{
    int a, b, c;
};
vector<ran>v;
void work(){
    cin >> n >> m;
    mem(tr, inf);
    for(int i = 1; i <= n; ++i)tr[i][i] = 0;
    for(int i = 1, a, b, c; i <= m; ++i){
        cin >> a >> b >> c;
        v.push_back({a, b, c});
        tr[a][b] = tr[b][a] = c;
        num[a][b] = num[b][a] = 1;
    }
    for(int k = 1; k <= n; ++k){
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j){
                if(tr[i][j] > tr[i][k] + tr[k][j]){
                    tr[i][j] = tr[i][k] + tr[k][j];
                    num[i][j] = num[i][k] * num[k][j];
                }
                else if(tr[i][j] == tr[i][k] + tr[k][j]){
                    num[i][j] += num[i][k] * num[k][j];
                }
            }
        }
    }
    int ans = 0;
    for(auto [a, b, c] : v){
        if(tr[a][b] < c || num[a][b] > 1)++ans;
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}

//间接计算
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
ll tr[505][505];
struct ran{
    int a, b, c;
};
void work(){
    cin >> n >> m;
    mem(tr, inf);
    for(int i = 1; i <= n; ++i)tr[i][i] = 0;
    for(int i = 1, a, b, c; i <= m; ++i){
        cin >> a >> b >> c;
        tr[a][b] = tr[b][a] = c;
    }
    for(int k = 1; k <= n; ++k){
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j){
                tr[i][j] = min(tr[i][j], tr[i][k] + tr[k][j]);
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            if(i == j)continue;
            int p = 1;
            for(int k = 1; k <= n; ++k){
                if(k != i && k != j && tr[i][j] == tr[i][k] + tr[k][j]){
                    p = 0;
                }
            }
            ans += p;
        }
    }
    cout << m - ans / 2 << endl;
}


int main(){
    io;
    work();
    return 0;
}