考虑删掉每条边会不会影响最短路之和
标记
暴力求解
#include#include #include #include const int N = 110;int dis[N], vis[N], Map[N][N], sum[N], used[N][N][N];int A[N * 30], B[N * 30];int n, m;std:: queue Q;inline int Bfs(int start, int opt) { for(int i = 1; i <= n; i ++) vis[i] = 0, dis[i] = 0; Q.push(start); vis[start] = 1; while(!Q.empty()) { int topp = Q.front(); Q.pop(); for(int i = 1; i <= n; i ++) { if(!vis[i] && (Map[topp][i] > 0 || Map[i][topp] > 0)) { vis[i] = 1; if(! opt) used[start][topp][i] = used[start][i][topp] = 1; dis[i] += dis[topp] + 1; Q.push(i); } } } int ret = 0; for(int i = 1; i <= n; i ++) { if(!dis[i] && i != start) return -1; ret += dis[i]; } return ret;}int main() { while(~ (scanf("%d%d", &n, &m))) { memset(Map, 0, sizeof Map); memset(used, 0, sizeof used); memset(sum, 0, sizeof sum); for(int i = 1; i <= m; i ++) { std:: cin >> A[i] >> B[i]; Map[A[i]][B[i]] ++, Map[B[i]][A[i]] ++; } int Flag = 0; for(int i = 1; i <= n; i ++) { sum[i] = Bfs(i, 0); if(sum[i] == -1) { Flag = -1; break; } else Flag += sum[i]; } for(int i = 1; i <= m; i ++) { int Nowtot = Flag; Map[A[i]][B[i]] --, Map[B[i]][A[i]] --; if(Map[A[i]][B[i]] > 0) std:: cout << Nowtot << "\n"; else if(Nowtot == -1) std:: cout << "INF\n"; else { bool flag = 0; for(int j = 1; j <= n; j ++) if(used[j][A[i]][B[i]] == 1) { Nowtot -= sum[j]; int tmp = Bfs(j, 1); if(tmp == -1) {flag = 1; break;} Nowtot += tmp; } if(flag) std:: cout << "INF\n"; else std:: cout << Nowtot << "\n"; } Map[A[i]][B[i]] ++, Map[B[i]][A[i]] ++; } } return 0;}