CF-1076

Posted on | Edited on | In | Views:

D. Edge Deletion

题意

the length of the shortest path from vertex 1 to vertex i as $d_i$ .

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

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

题解

先跑个最短路，再搜索，取最短路上的边。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
#define forl(i, l, r) for (int i = l; i <= r; i++)
#define forr(i, r, l) for (int i = r; i >= l; i--)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define for0(i, n) for (int i = 0; i < n; i++)
#define meminf(a) memset(a, inf, sizeof(a))
#define mem_1(a) memset(a, -1, sizeof(a))
#define mem0(a) memset(a, 0, sizeof(a))
#define inlld(lld) scanf("%lld", &lld)
#define inlf(f) scanf("%lf", &f)
#define ind(d) scanf("%d", &d)
#define ins(s) scanf("%s", s)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
typedef std::pair<long long, long long> pll;
typedef std::pair<int, int> pii;
typedef unsigned long long ull;
typedef long double db;
typedef long long ll;
const db pi = acos(-1.0);
const ll inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 3.1e5;
const db eps = 1e-8;
using namespace std;
int sign(db a) { return a < -eps ? -1 : a > eps; }
int db_cmp(db a, db b) { return sign(a - b); }

struct Edge {
    int v, w, nxt, no;
} edge[2 * N];
int fir[N], cnt;
void addedge(int u, int v, int w, int no) {
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].nxt = fir[u];
    edge[cnt].no = no;
    fir[u] = cnt++;
}
struct node {
    int u;
    ll d;
    node(int u, ll d) : u(u), d(d) {}
    bool operator<(const node &a) const { return d > a.d; }
};
bool used[N];
ll d[N];
void dijkstra() {
    priority_queue<node> que;
    meminf(d);
    d[1] = 0;
    que.push(node(1, d[1]));
    while (!que.empty()) {
        int u = que.top().u;
        que.pop();
        if (used[u]) continue;
        used[u] = 1;
        for (int i = fir[u]; i != -1; i = edge[i].nxt) {
            int v = edge[i].v;
            int w = edge[i].w;
            if (used[v]) continue;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                que.push(node(v, d[v]));
            }
        }
    }
}
bool used_edge[N];
void init() {
    mem_1(fir);
    cnt = 0;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("/Users/perpeternal/Documents/Sketch/data/in.dat", "r", stdin);
    // freopen("/Users/perpeternal/Documents/Sketch/data/out.dat", "w", stdout);
#endif
    // ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    init();
    int n, m, k, u, v, w;
    scanf("%d%d%d", &n, &m, &k);
    for1(i, m) {
        scanf("%d%d%d", &u, &v, &w);
        addedge(u, v, w, i);
        addedge(v, u, w, i);
    }
    if (k == 0) {
        puts("0\n");
        return 0;
    }
    dijkstra();
    queue<int> que;
    que.push(1);
    mem0(used);
    used[1] = 1;
    int ans = 0;
    while (que.size()) {
        int u = que.front();
        que.pop();
        for (int i = fir[u]; i != -1; i = edge[i].nxt) {
            int v = edge[i].v;
            int w = edge[i].w;
            if (used[v]) continue;
            if (d[v] == d[u] + w) {
                used_edge[edge[i].no] = 1;
                used[v] = 1;
                ans++;
                if (ans == k) break;
                que.push(v);
            }
        }
        if (ans == k) break;
    }
    printf("%d\n", ans);
    for1(i, m) {
        if (used_edge[i]) printf("%d ", i);
    }
    puts("");
    return 0;
}

E. Vasya and a Tree

题意

给一颗树，将 v 和与 v 距离小于 d 的 v 的子节点的权值加上 x，输出所有节点的权值。

题解

保存每个点每次加权的终点和 x。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
#define forl(i, l, r) for (int i = l; i <= r; i++)
#define forr(i, r, l) for (int i = r; i >= l; i--)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define for0(i, n) for (int i = 0; i < n; i++)
#define meminf(a) memset(a, inf, sizeof(a))
#define mem_1(a) memset(a, -1, sizeof(a))
#define mem0(a) memset(a, 0, sizeof(a))
#define inlld(lld) scanf("%lld", &lld)
#define inlf(f) scanf("%lf", &f)
#define ind(d) scanf("%d", &d)
#define ins(s) scanf("%s", s)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
typedef std::pair<long long, long long> pll;
typedef std::vector<long long> vll;
typedef std::pair<int, int> pii;
typedef unsigned long long ull;
typedef std::vector<int> vi;
typedef long double db;
typedef long long ll;
const db pi = acos(-1.0);
const ll inf =0x3f3f3f3f;
const ll mod = 1e9+7;
const int N = 3.1e5;
const db eps = 1e-8;
using namespace std;
int sign(db a) { return a < -eps ? -1 : a > eps; }
int db_cmp(db a, db b){ return sign(a-b); }

vi node[N];
int dep[N];
ll change[N];
bool vis[N];
int maxx;

void dfs(int r,int dph){
    dep[r]=dph;
    vis[r]=1;
    maxx=max(maxx,dph);
    for(int v:node[r])if(vis[v]==0)dfs(v,dph+1);
}
struct da{
    int end,x;
    da(){}
    da(int a,int b):end(a),x(b){}
};
vector<da> weight[N];
ll tmpc[N];
void ddfs(int r,int depth,ll sum){
    for(auto i:weight[r]){
        sum+=i.x;
        tmpc[i.end]+=i.x;
    }
    change[r]+=sum;
    sum-=tmpc[depth];
    vis[r]=1;
    for(int v:node[r])if(vis[v]==0)ddfs(v,depth+1,sum);
    for(auto i:weight[r])tmpc[i.end]-=i.x;
}
int main() {
#ifdef PerpEternal
    // freopen("/Users/perpeternal/Documents/Sketch/data/in.dat", "r", stdin);
    // freopen("/Users/perpeternal/Documents/Sketch/data/out.dat", "w", stdout);
#endif
    //ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,m,u,v,d,x;
    ind(n);
    for0(i,n-1){
        scanf("%d%d",&u,&v);
        node[u].push_back(v);
        node[v].push_back(u);
    }
    dfs(1,1);
    ind(m);
    for0(i,m){
        scanf("%d%d%d",&v,&d,&x);
        weight[v].push_back(da(min(dep[v]+d,maxx),x));
    }
    mem0(vis);
    ddfs(1,1,0);
    for1(i,n)printf("%lld ",change[i]);
    puts("");
    return 0;
}