题解：P16442 [XJTUPC 2026] 机房分配

xiaozhengguoaaa · 2026-05-10 21:43:44 · 题解

有点鸽巢原理感觉。

思路及证明

一、思路

1. 题目一定有解。
2. 依次遍历每个点，逐个分配机房。
3. 对当前点，只看已经分配过的邻点；若把当前点放进某机房，产生的额外风险是该机房内已有邻点的边权和。
4. 贪心每次把当前点分配到额外风险增量最小的机房。
5. 用 multiset 维护各机房当前总风险，快速取最小值、维护更新。

二、证明

设所有边总权和为 S，把每条边的贡献看成若边两点同机房，则计入总风险和，否则不计。

设最终总风险和为 T，等价于求：将顶点划分为 k 组，组内边权总和 T 的上界。

采用平均分配鸽巢原理：

任意一条边，无论怎么划分，只会被至多一个机房计入风险。

每一步分配时，将当前点放入使新增代价最小的组，等价于把边的贡献均匀分摊到 k 个机房。

对所有边整体平均： 平均每个机房分摊的边权和为 \dfrac{S}{k}。

由鸽巢原理，存在一种划分使得总风险和不超过上取整：

::::info[AC code]

#include <bits/stdc++.h>
#define int long long
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;

const int N = 500005;

inline int read()
{
    int s = 0 , w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
        {
            w = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * w;
}
inline void write(int x)
{
    if (x < 0)
    {
        putchar('-') , x = -x;
    }
    if (x > 9)
    {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}

vector<pair<int , ll>> g[N];

int a[N];

ll r[N];

bool v[N];

signed main()
{
    fst;
    int n = read() , m = read() , k = read();
    for (int i = 1 ; i <= m ; i ++)
    {
        int u = read() , v = read();
        ll w = read();
        g[u].push_back({v , w});
        g[v].push_back({u , w});
    }
    multiset<pair<ll , int>> s;
    for (int i = 1 ; i <= k ; i ++)
    {
        s.insert({0 , i});
    }
    for (int i = 1 ; i <= n ; i ++)
    {
        vector<pair<int , ll>> t;
        for (auto &e : g[i])
        {
            int u = e.first;
            ll w = e.second;
            if (v[u])
            {
                int p = a[u];
                t.push_back({p , w});
            }
        }
        for (auto &p : t)
        {
            int o = p.first;
            ll w = p.second;
            s.erase({r[o] , o});
            r[o] += w;
            s.insert({r[o] , o});
        }
        auto b = *s.begin();
        int c = b.second;
        a[i] = b.second;
        v[i] = true;
        for (auto &p : t)
        {
            int o = p.first;
            ll w = p.second;
            s.erase({r[o] , o});
            r[o] -= w;
            s.insert({r[o] , o});
        }
        ll d = 0;
        for (auto &p : t)
        {
            if (p.first == c)
            {
                d += p.second;
            }
        }
        s.erase({r[c] , c});
        r[c] += d;
        s.insert({r[c] , c});
    }
    cout << "Yes" << endl ;
    for (int i = 1 ; i <= n ; i ++)
    {
        cout << a[i] ;
        cout << ' ' ;
    }
    return 0;
}