Skip to content

构造训练

对于构造题，基本思路就是先证明有解的条件，方法有很多，数学归纳法，鸽巢原理等，通常具体的构造方法也是基于有解的证明之上。

CF1515F

注意到最后一条道路的要求是确定的：\(\sum_{i=1}^{n}a[i]\geq(n-1)*x\) ，其中 \(n\) 表示图中的结点数。不妨猜测对任意的连通图，该条件是有解的充要条件。

证明考虑随意取一颗生成树，我们从任意叶子 \(u\) 开始，考虑它连接的唯一点 \(v\) ，如果 \(a[u]+a[v]\geq x\) ，那么修建该道路，同时删去结点 \(u\) ，修改点 \(v\) 权值为 \(a[u]+a[v]-x\) ，注意这样操作上述不等式依旧成立。 如果不能修建道路，还是考虑删去点 \(u\) ，同时将 \(u\) 压入栈中，表示我们最后修建这条连接 \(u\) 的道路，上述不等式保证一定能修建成功，同时注意此时一定有 \(a[u]<x\) ，删去点后的新图不等式依旧成立。 当图删得只剩两个点时，不等式退化为 \(a[u]+a[v]>=x\) ，此时一定能修建成功，同时我们不断弹出栈中结点来修建道路即可。

代码实现就是按照上述证明做拓扑排序，值得一提的是该题可以推广到边带权的情形。条件变为 \(\sum_{i=1}^{n}a[i]\geq val\) ，\(val\) 表示最小生成树的权值。

代码 
 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
#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 3e5 + 10;
vector<pair<int, int>>e[N];
int n, m, x, f[N], d[N];
ll a[N], sum;
bool st[N];

int find(int x) {
    if (f[x] != x)f[x] = find(f[x]);
    return f[x];
}

void solve()
{
    cin >> n >> m >> x;
    for (int i = 1; i <= n; i++)f[i] = i, cin >> a[i], sum += a[i];
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        if (find(u) == find(v))continue;
        f[find(u)] = find(v);
        e[u].push_back({v, i});
        e[v].push_back({u, i});
        d[u]++, d[v]++;
    }

    if (sum < 1ll * (n - 1) * x) {
        cout << "NO\n";
        return;
    }
    else cout << "YES\n";

    queue<int>q;
    vector<int>stk, ans;
    for (int i = 1; i <= n; i++)if (d[i] == 1)q.push(i);
    while (!q.empty())
    {
        int u = q.front(); q.pop();
        st[u] = 1;
        for (auto [v, pos] : e[u])
        {
            if (st[v])continue;
            d[v]--;
            if (d[v] == 1)q.push(v);
            if (a[u] + a[v] >= x)ans.push_back(pos), a[v] += a[u] - x;
            else stk.push_back(pos);
        }
    }

    ans.insert(ans.end(), stk.rbegin(), stk.rend());
    for (auto k : ans)cout << k << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    while (t--)solve();
    return 0;
}