CF1076D Edge Deletion 最短路径树+bfs

谁践踏了优雅 2021-12-16 19:55 307阅读 0赞

## 题目描述 ##

You are given an undirected connected weighted graph consisting of n n n vertices and m m m edges. Let's denote the length of the shortest path from vertex 1 1 1 to vertex i i i as di d\_i di .

You have to erase some edges of the graph so that at most k k k edges remain. Let's call a vertex i i i good if there still exists a path from 1 1 1 to i i i with length di d\_i di after erasing the edges.

Your goal is to erase the edges in such a way that the number of good vertices is maximized.

## 输入输出格式 ##

**输入格式：**

The first line contains three integers n n n , m m m and k k k ( 2≤n≤3⋅105 2 \\le n \\le 3 \\cdot 10^5 2≤n≤3⋅105 , 1≤m≤3⋅105 1 \\le m \\le 3 \\cdot 10^5 1≤m≤3⋅105 , n−1≤m n - 1 \\le m n−1≤m , 0≤k≤m 0 \\le k \\le m 0≤k≤m ) — the number of vertices and edges in the graph, and the maximum number of edges that can be retained in the graph, respectively.

Then m m m lines follow, each containing three integers x x x , y y y , w w w ( 1≤x,y≤n 1 \\le x, y \\le n 1≤x,y≤n , x≠y x \\ne y x≠y , 1≤w≤109 1 \\le w \\le 10^9 1≤w≤109 ), denoting an edge connecting vertices x x x and y y y and having weight w w w .

The given graph is connected (any vertex can be reached from any other vertex) and simple (there are no self-loops, and for each unordered pair of vertices there exists at most one edge connecting these vertices).

**输出格式：**

In the first line print e e e — the number of edges that should remain in the graph ( 0≤e≤k 0 \\le e \\le k 0≤e≤k ).

In the second line print e e e distinct integers from 1 1 1 to m m m — the indices of edges that should remain in the graph. Edges are numbered in the same order they are given in the input. The number of good vertices should be as large as possible.

## 输入输出样例 ##

**输入样例\#1：** 复制

3 3 2
    1 2 1
    3 2 1
    1 3 3

**输出样例\#1：** 复制

2
    1 2

**输入样例\#2：** 复制

4 5 2
    4 1 8
    2 4 1
    2 1 3
    3 4 9
    3 1 5

**输出样例\#2：** 复制

2
    3 2 
    
    n 个点 m条边的连通图，只能最多保留K条边，最后要满足从1出发到其他节点最短距离不变的点最多，问方案（边）
    先 dijkstra 一下，保存一下父亲和儿子节点以及边的编号；
    最后 bfs一下，每次如果此时的 K>0，那么就选择改边；

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstdlib>
    #include<cstring>
    #include<string>
    #include<cmath>
    #include<map>
    #include<set>
    #include<vector>
    #include<queue>
    #include<bitset>
    #include<ctime>
    #include<deque>
    #include<stack>
    #include<functional>
    #include<sstream>
    //#include<cctype>
    //#pragma GCC optimize("O3")
    using namespace std;
    #define maxn 400005
    #define inf 0x3f3f3f3f
    #define INF 9999999999
    #define rdint(x) scanf("%d",&x)
    #define rdllt(x) scanf("%lld",&x)
    #define rdult(x) scanf("%lu",&x)
    #define rdlf(x) scanf("%lf",&x)
    #define rdstr(x) scanf("%s",x)
    typedef long long  ll;
    typedef unsigned long long ull;
    typedef unsigned int U;
    #define ms(x) memset((x),0,sizeof(x))
    const long long int mod = 1e9 + 7;
    #define Mod 1000000000
    #define sq(x) (x)*(x)
    #define eps 1e-3
    typedef pair<int, int> pii;
    #define pi acos(-1.0)
    const int N = 1005;
    #define REP(i,n) for(int i=0;i<(n);i++)
    typedef pair<int, int> pii;
    inline ll rd() {
    	ll x = 0;
    	char c = getchar();
    	bool f = false;
    	while (!isdigit(c)) {
    		if (c == '-') f = true;
    		c = getchar();
    	}
    	while (isdigit(c)) {
    		x = (x << 1) + (x << 3) + (c ^ 48);
    		c = getchar();
    	}
    	return f ? -x : x;
    }
    
    ll gcd(ll a, ll b) {
    	return b == 0 ? a : gcd(b, a%b);
    }
    ll sqr(ll x) { return x * x; }
    
    /*ll ans;
    ll exgcd(ll a, ll b, ll &x, ll &y) {
    	if (!b) {
    		x = 1; y = 0; return a;
    	}
    	ans = exgcd(b, a%b, x, y);
    	ll t = x; x = y; y = t - a / b * y;
    	return ans;
    }
    */
    
    
    
    ll qpow(ll a, ll b, ll c) {
    	ll ans = 1;
    	a = a % c;
    	while (b) {
    		if (b % 2)ans = ans * a%c;
    		b /= 2; a = a * a%c;
    	}
    	return ans;
    }
    
    int n, m, k;
    int head[maxn<<1];
    struct node {
    	int to;
    	ll dis;
    	node(){}
    	node(int to,ll dis):to(to),dis(dis){}
    
    	bool operator < (const node&rhs)const {
    		return dis > rhs.dis;
    	}
    }edge[maxn<<1];
    
    struct Edge {
    	int id;
    	int v; ll w;
    	int nxt;
    
    	Edge(){}
    	Edge(int id,int v,int w):id(id),v(v),w(w){}
    
    }EDGE[maxn<<1];
    
    ll dis[maxn];
    bool vis[maxn];
    int fath[maxn], fathedge[maxn];
    vector<Edge>G[maxn];
    
    void addedge(int i, int u, int v, int w) {
    	G[u].push_back(Edge(i, v, w)); G[v].push_back(Edge(i, u, w));
    }
    
    priority_queue<node>pq;
    
    void dijkstra() {
    	memset(dis, 0x3f, sizeof(dis)); ms(vis);
    	dis[1] = 0; vis[1] = 0;
    	fath[1] = 1;
    	pq.push(node(1, 0));
    	while (!pq.empty()) {
    		node tmp = pq.top(); pq.pop();
    		int u = tmp.to;
    		if (vis[u])continue; vis[u] = 1;
    		for (int i = 0; i < G[u].size(); i++) {
    			int v = G[u][i].v;
    			if (dis[v] > dis[u] + (ll)G[u][i].w) {
    				dis[v] = dis[u] + (ll)G[u][i].w;
    				fath[v] = u; fathedge[v] = G[u][i].id;
    				pq.push(node(v, (ll)dis[v]));
    			}
    		}
    	}
    }
    
    vector<int>son[maxn];
    vector<int>res;
    queue<int>q;
    
    void bfs() {
    	q.push(1);
    	while (!q.empty()) {
    		int u = q.front(); q.pop();
    		for (int i = 0; i < son[u].size(); i++) {
    			int v = son[u][i];
    			if (k > 0) {
    				res.push_back(fathedge[v]); q.push(v); k--;
    			}
    			else
    				break;
    		}
    	}
    }
    
    
    int main()
    {
    	//ios::sync_with_stdio(0);
    	rdint(n); rdint(m); rdint(k);
    	for (int i = 1; i <= m; i++) {
    		int u, v, w; rdint(u); rdint(v); rdint(w);
    		addedge(i, u, v, w);
    	}
    	dijkstra();
    	for (int i = 2; i <= n; i++) {
    		son[fath[i]].push_back(i);
    	}
    	bfs();
    	cout << res.size() << endl;
    	for (int i = 0; i < res.size(); i++) {
    		cout << res[i] << ' ';
    	}
    	cout << endl;
        return 0;
    }

转载于:https://www.cnblogs.com/zxyqzy/p/9955736.html