Codeforces 1076D Edge Deletion——最短路+dfs 图论

题意：
n个点m条边的无向连通图（无自环、重边），现在要删除一些边使得图最多剩下k条边，并且这样的点尽量多：这个点到1号节点的最短路不变
思路：
建出最短路树，统计边数，然后跑一遍dfs，在回溯的时候判断边数与k的关系，若边数>k就使边数减一，否则记录答案

#include using namespace std; const int maxn = 3e5 + 10; typedef long long ll; const ll INF = 1e16; typedef pair P; int n, m, k; int tot, head[maxn]; struct Edge { int to, cost, id, next; }edges[2*maxn]; void init_edges() { tot = 0; memset(head, -1, sizeof(head)); } void addedge(int from, int to, int cost, int id) { edges[tot].to = to; edges[tot].cost = cost; edges[tot].id = id; edges[tot].next = head[from]; head[from] = tot++; } bool vis[maxn]; ll dis[maxn]; struct Path { int to; int id; }path[maxn]; void dijkstra() { memset(vis, 0, sizeof(vis)); for (int i = 0; i < maxn; i++) dis[i] = INF; memset(path, 0, sizeof(path)); int s = 1; dis[s] = 0; priority_queue, greater > que; que.push(make_pair(0, s)); while (!que.empty()) { int u = que.top().second; que.pop(); if (vis[u]) continue; vis[u] = 1; for (int i = head[u]; ~i; i = edges[i].next) { int v = edges[i].to, cost = edges[i].cost, id = edges[i].id; if (dis[v] > dis[u] + cost) { dis[v] = dis[u] + cost; path[v].to = u; path[v].id = id; que.push(make_pair(dis[v], v)); } } } } int cnt; void dfs(int u) { if (u == 0) return; if (vis[u]) return; vis[u] = 1; int v = path[u].to, id = path[u].id; if (v == 0) return; addedge(v, u, 1, id); cnt++; dfs(v); } vector ans; void solve(int u) { for (int i = head[u]; ~i; i = edges[i].next) { int v = edges[i].to, id = edges[i].id; solve(v); if (cnt > k) { cnt--; } else { ans.push_back(id); } } } int main() { scanf("%d%d%d", &n, &m, &k); init_edges(); for (int i = 1; i <= m; i++) { int u, v, cost; scanf("%d%d%d", &u, &v, &cost); addedge(u, v, cost, i); addedge(v, u, cost, i); } dijkstra(); cnt = 0; init_edges(); memset(vis, 0, sizeof(vis)); for (int i = 2; i <= n; i++) { dfs(i); } ans.clear(); solve(1); sort(ans.begin(), ans.end()); printf("%d\n", ans.size()); for (int i = 0; i < ans.size(); i++) { printf("%d", ans[i]); if (i == ans.size()-1) printf("\n"); else printf(" "); } return 0; }

【Codeforces 1076D Edge Deletion——最短路+dfs】