abc243 E(还久内阁摆烂)

题目 题意: 给定n个点m条边的简单图，初始保证连通，你需要删除尽可能多的边。 删边的要求: 1.删除该边后该图仍然连通。 2.删除该边后任意两点之间的最短距离不变。 思路: 正难则反，真删确实有点难写。但是可以考虑哪些边必不能删除，如果删除后不连通或者最短路改变，就不能删除。通过floyd预处理最短路。枚举两点(i,j)和中间点k，如果dist[i][j] 可以通过 dist[i][k] + dist[k][j]得到，那么说明存在过渡点k从i走到j，这条边没有存在的必要。如果删除该边后会导致不连通，那么说明i、j两点之间的最短路恰好是该边的边权，所以判断该边不能删除。 时间复杂度: O(n^3) 代码:

// Problem: E - Edge Deletion
// Contest: AtCoder - AtCoder Beginner Contest 243
// URL: https://atcoder.jp/contests/abc243/tasks/abc243_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i