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

· · 题解

官方题解里说的比较清楚，也就是每次分配时取风险增加量的最小值，每次增加量不会超过它与所有其他边全值的平均值。

这里给一个比较抽象的概率上的理解，现在假设所有同学都是随机分机房的，考虑 i,j 两名同学，那么他们分在同一组的概率

P=k\times\dfrac 1k\times\dfrac1k=\dfrac1k

假设 x_{ij}=\begin{cases}w_{ij},&(i,j)\in E\\0,&(i,j)\not\in E\end{cases}，那么在考虑第 i 位同学的分组时，风险增加值的期望为

E_i=\dfrac1k\sum_{(i,j)\in E}w_{ij}

因此对 i 求和得到总的风险期望

E = \dfrac1k\sum_{(i,j)\in E}w_{ij} = \dfrac Sk

因此一定存在不比期望高的分配方案，故存在一种方案使得风险值之和不超过 \left\lceil\dfrac Sk\right\rceil，答案一定是 \texttt{Yes}。

只需要贪心地每次选择风险值最小的那一组分配即可。参考代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

inline int read() {
    int num = 0, nev = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') nev = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { num = num * 10 + (ch - '0'); ch = getchar(); }
    return num * nev;
}

struct edge{
    int to, w;
};

struct node{
    int g, w;    //分组，权值
};

int cmp(const node &a, const node &b) {
    return a.g < b.g;
}

const int maxn = 5e5 + 5;
vector<edge> G[maxn];
int group[maxn];
signed main() {
    int n = read(), m = read(), k = read();
    for (int i = 1; i <= m; i ++) {
        int u = read(), v = read(), w = read();
        G[u].push_back((edge){v, w});
        G[v].push_back((edge){u, w});
    }

    for (int u = 1; u <= n; u ++) {
        vector<node> nei;   //与u存在边的近邻
        for (edge e : G[u]) {
            int v = e.to;
            int w = e.w;
            if (group[v]) {
                nei.push_back((node){group[v], w});
            }
        }
        sort(nei.begin(), nei.end(), cmp);

        vector<node> tmp;   //对nei进行去重，相同组的合并
        for (int i = 0; i < nei.size(); i ++) {
            if (i == 0 || nei[i].g != nei[i-1].g) {
                tmp.push_back(nei[i]);
            } else {
                tmp.back().w += nei[i].w;
            }
        }

        if (tmp.size() == k) {   //如果与u相邻的点都已经分好组且没有其它组可分
            int minc = 1e17, gr = 0;
            for (int i = 0; i < tmp.size(); i ++) {
                if (tmp[i].w < minc) {
                    minc = tmp[i].w;
                    gr = tmp[i].g;
                }
            }
            group[u] = gr;
        } else {
            int cur = 1;
            for (int i = 0; i < tmp.size(); i ++) {
                if (cur < tmp[i].g) break;
                else cur = tmp[i].g + 1;
            }
            group[u] = cur;
        }
    }

    puts("Yes");
    for (int i = 1; i <= n; i ++) {
        cout << group[i] << ' ';
    }
    return 0;
}