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

· · 题解

这种带上取整的构造题大概率是一定有解的。直接构造难以入手，考虑增量构造。

初始先划分 1\sim k，每个集合一个点。然后对于 u\in[k+1,n]，找当前所有集合中和 u 连边权值和最小的那个，把 u 放进去。显然每次新增的权值和都占总权值的不到 \frac 1k，所以必定合法。

:::info[代码]

#include<bits/stdc++.h>
#define il inline
#define ui unsigned int
#define ll long long
#define ull unsigned ll
#define lll __int128
#define db double
#define ldb long double
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define fir first
#define sec second
#define gc getchar
#define pc putchar
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pct __builtin_popcount
#define mst(a,x) memset(a,x,sizeof a)
#define mcp(a,b) memcpy(a,b,sizeof b)
using namespace std;
const int N=5e5+10,INF=0x3f3f3f3f,MOD=998244353;
const ll INFll=0x3f3f3f3f3f3f3f3f;
il int rd() {int x=0,f=1; char ch=gc(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f;}
il ll rdll() {ll x=0; int f=1; char ch=gc(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f;}
il void wr(int x) {if(x==INT_MIN) return printf("-2147483648"),void(); if(x<0) return pc('-'),wr(-x); if(x<10) return pc(x+'0'),void(); wr(x/10),pc(x%10+'0');}
il void wrll(ll x) {if(x==LLONG_MIN) return printf("-9223372036854775808"),void(); if(x<0) return pc('-'),wrll(-x); if(x<10) return pc(x+'0'),void(); wrll(x/10),pc(x%10+'0');}
il void wr(int x,const char *s) {wr(x),printf("%s",s);}
il void wrll(ll x,const char *s) {wrll(x),printf("%s",s);}
il int vmod(int x) {return x>=MOD?x-MOD:x;}
il int vadd(int x,int y) {return vmod(x+y);}
il int vsub(int x,int y) {return vmod(x-y+MOD);}
il int vmul(int x,int y) {return 1ll*x*y%MOD;}
il int qpow(int x,int y) {int r=1; for(;y;y>>=1,x=vmul(x,x)) if(y&1) r=vmul(r,x); return r;}
il void cadd(int &x,int y) {x=vmod(x+y);}
il void csub(int &x,int y) {x=vmod(x-y+MOD);}
il void cmul(int &x,int y) {x=vmul(x,y);}
il void cmax(int &x,int y) {x<y&&(x=y);}
il void cmaxll(ll &x,ll y) {x<y&&(x=y);}
il void cmin(int &x,int y) {x>y&&(x=y);}
il void cminll(ll &x,ll y) {x>y&&(x=y);}
int n,m,k,id,hd[N],bk[N];
struct EDGE {int to,w,ne;} e[N*2];
il void add(int u,int v,int w) {e[++id]={v,w,hd[u]},hd[u]=id;}
ll s[N];
multiset<pair<ll,int>> st;
void QwQ() {
    n=rd(),m=rd(),k=rd();
    for(int u,v,w;m--;) u=rd(),v=rd(),w=rd(),add(u,v,w),add(v,u,w);
    for(int i=1;i<=k;i++) bk[i]=i,st.insert({0,i});
    for(int u=k+1;u<=n;u++) {
        for(int i=hd[u],v;i;i=e[i].ne) if((v=e[i].to)<u) {
            st.erase(st.find({s[bk[v]],bk[v]}));
            s[bk[v]]+=e[i].w;
            st.insert({s[bk[v]],bk[v]});
        }
        auto [x,y]=*st.begin();
        bk[u]=y;
        for(int i=hd[u],v;i;i=e[i].ne) if((v=e[i].to)<u) {
            st.erase(st.find({s[bk[v]],bk[v]}));
            s[bk[v]]-=e[i].w;
            st.insert({s[bk[v]],bk[v]});
        }
    }
    puts("Yes");
    for(int i=1;i<=n;i++) wr(bk[i]," ");
}
signed main() {
//  freopen("in.in","r",stdin),freopen("out.out","w",stdout);
    int T=1; while(T--) QwQ();
}

:::