526互联

AtCoder Beginner Contest 218

发布时间 2023-09-13 17:03:57作者: zhujio
[ABC218E] Destruction

题意翻译

给一个无向图，让你从中选出几个边，要求选出的边权总和最大并且剩下的图要是一个连通图，输出最大的边权。

 

贪心的想剩下来的图一定是一个树结构，那么要满足去掉的边权和大，就可以想到最小生成树，用总边权减去最小生成树就是答案

 

[ABC218F] Blocked Road

题面翻译

给定一张 n 个点，m 条边的有向图，每条边的边权均为 1。请对于每一个$i\in [1,m]$求出从点 1 到 n 的不经过第 i 条边的最短路长度。

 

最朴素的做法是枚举每条边被删去后进行$\space bfs\space$复杂度就是$\space O(m \times \space (n + \space m))$

对于稠密图$\space m\space = n ^ 2$，显然这样子复杂度是$\space O(n^4)$

最短路上边最多$\space n - 1\space $条，也就是说我们只需要关心这条最短路上的边，删去其他边并不会改变最短路长度

所以这样子复杂度是$\space O(n \times \space (n + \space m))$，对于稠密图复杂度是$\space O(n^3)$

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 200100;
const int inf = INT_MAX / 2;

int n, m, vis[N], dist[N], pre[N];
vector<int> edge[N];
array<int, 2> e[N];

int bfs(int not_go){
    queue<int> q; q.push(1);
    for(int i = 1; i <= n; i++) dist[i] = inf, vis[i] = 0;
    dist[1] = 0, vis[1] = 1;
    while(!q.empty()) {
        auto x = q.front(); q.pop();
        for(auto y : edge[x]) {
            if(e[not_go] == (array<int, 2>){x, y}) continue;
            if(dist[y] > dist[x] + 1) {
                dist[y] = dist[x] + 1;
                q.push(y);
                if(!not_go) pre[y] = x;
            }
        }
    }
    if(dist[n] >= inf) return -1;
    return dist[n];
}

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int x, y; cin >> x >> y;
        edge[x].push_back(y);
        e[i] = {x, y};
    }
    int ans = bfs(0), now = n;
    map<pair<int, int>, int> mp;
    while(now != 1) {
        if(!pre[now]) break;
        int x = pre[now];
        mp[{x, now}] = 1;
        now = pre[now];
    }
    if(now != 1) ans = -1;
    for(int i = 1; i <= m; i++) {
        if(!mp[{e[i][0], e[i][1]}]) cout << ans << endl;
        else cout << bfs(i) << endl;
    }
    return 0;
}
View Code