CF1076D Edge Deletion

原题链接

• 题意：给一个 (n) 个点,(m) 条边的无向简单带权连通图, 要求删边至最多剩余 (k) 条边.定义"好点"是指删边后, 1号节点到它的最短路长度仍然等于原图最短路长度的节点.最大化删边后的好点个数.
• 题解：求出来最短路径树，然后就选 (k) 个点或者不选之类的就行。
• 代码：

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const ll N = 1e6 + 99;
ll mod = 1e9 + 7;
const ll maxn = 1e7;
struct edge {
    ll v, w, id;
    ll u;
};
bool cmp(edge a, edge b) {
    return a.w < b.w;
}
ll d[N]; 
struct Node {
    ll pos, dis;
    bool operator<(Node rhs)const {
        return rhs.dis < dis;
    }
};
priority_queue<Node>pq;
vector<edge> G[N];
bool vis[N];
bool ans[N];
ll W[N];
ll pre[N];
bool choose[N];
void dij(ll s) {
    memset(d, 0x3f, sizeof d);
    d[s] = 0;
    pq.push({s, d[s]});
    memset(vis, 0, sizeof vis);
    while (!pq.empty()){
        auto now = pq.top();
        pq.pop();
        ll u = now.pos;
        if (vis[u])continue;
        vis[u] = 1;
        for (auto e:G[u]) {
            if (d[e.v] > d[u] + e.w ) {
                d[e.v] = d[u] + e.w;
                ans[pre[e.v]] = 0;
                pre[e.v] = e.id;
                pq.push({e.v, d[e.v]});
                ans[e.id] = 1;
            } else if (d[e.v] == d[u] + e.w) {//这是关键，求出最短路径树，就是最短的那个前驱边
                if (W[pre[e.v]] > e.w) {
                    ans[pre[e.v]] = 0;
                    pre[e.v] = e.id;
                    ans[pre[e.v]] = 1;
                }
            }
        }
    }
}
ll n, m, k;
ll sum = 0;
int cnt = 0;
void dfs(ll u) {
    for (auto e:G[u]) {
        if ( cnt < k && ans[e.id] && !choose[e.id]) {
            choose[e.id] = 1;
            cnt++;
            dfs(e.v);
        }
    }
}
void solve() {
    cin >> n >> m >> k;
    for (ll i = 1; i <= m; i ++) {
        ll u, v, w;
        cin >> u >>v >> w;
        G[u].push_back({v, w, i});
        G[v].push_back({u, w, i});
        W[i] = w;
    }
    ll s =  1;
    dij(s);
    for (ll i = 1; i <= m; i ++) {
        if (ans[i])sum++;
    }
    if (sum <= k) {
        cout << min(sum, k) << endl;
        for (ll i = 1;k >0 && i <= m; i ++) {
            if (ans[i]) {
                cout << i << " ";
                k--;
            }
        }   
    } else {
        cout << k << endl;
        dfs(1);
        for (ll i = 1; i <= m; i++) {
            if (choose[i]) {
                cout << i << " ";
            }
        }
    }
}
signed main() {
    ll t = 1;
    ios::sync_with_stdio(0);
    while (t--) solve();
    return 0;
}