![打卡信奥刷题（3648）用C++实现信奥题 P12042 [USTCPC 2025] 图上交互题 3 / Constructive Maximum Mex Path](http://pic.xiahunao.cn/yaotu/打卡信奥刷题（3648）用C++实现信奥题 P12042 [USTCPC 2025] 图上交互题 3 / Constructive Maximum Mex Path)
P12042 [USTCPC 2025] 图上交互题 3 / Constructive Maximum Mex Path题目背景USTCPC 设置 3s 时限为了使得 python 通过。洛谷改为 1s 时限。2024 年 12 月 28 日 14:59:50随着最后一发 E 题的提交出现了 Wrong Answer小 G 的 EC-Final 比赛结束了。小 G 的 EC-Final 连续两年都在不同的细节题上倒闭了。克露丝卡尔酱想要帮助她的同学小 G很可惜细节题是不能批量生产的但刚好克露丝卡尔酱想到了这样一个细节题考验大家的细节题能力。希望大家不要在细节题上倒闭为什么这个系列的题目还在继续呢题目描述给定一个nnn个点mmm条边的无向图。第iii条边(ui,vi)(u_i,v_i)(ui,vi)有一个未知边权aia_iai。对于任何一条路径定义其代价如下设路径为(p0,p1,...,pk)(p_0,p_1,...,p_k)(p0,p1,...,pk)其中要求(pi−1,pi)(p_{i-1},p_i)(pi−1,pi)是无向图中的边设其为第eie_iei条边。那么路径的代价即为mexi1kaei\mathop{\text{mex}}\limits_{i1}^{k} a_{e_i}i1mexkaei。该路径可以经过重复点和重复边即ppp和eee可以包含重复的数mex\text{mex}mex是一种定义域为一个非负整数的可重集合函数值为非负整数的映射定义为集合内最小未在集合内出现过的非负整数。定义f(x,y)f(x,y)f(x,y)为从xxx到yyy的所有路径中代价的最大值。给定n,mn,mn,m再对于每条边(ui,vi)(u_i,v_i)(ui,vi)给定f(ui,vi)f(u_i,v_i)f(ui,vi)你需要求出是否存在一组合法的aia_iai如果有解你还需要构造一组解。输入格式第一行两个正整数n,mn,mn,m(1≤n,m≤105)(1\le n,m\le 10^5)(1≤n,m≤105)。第2∼m12\sim m12∼m1行每行两个正整数ui,viu_i,v_iui,vi(1≤ui,vi≤n)(1\le u_i,v_i\le n)(1≤ui,vi≤n)和一个非负整数f(ui,vi)f(u_i,v_i)f(ui,vi)(0≤f(ui,vi)231)(0\le f(u_i,v_i)2^{31})(0≤f(ui,vi)231)。请注意本题并不保证图连通可能会存在重边和自环。输出格式如果不存在解则仅输出No。否则在第一行输出Yes在第二行输出mmm个非负整数aia_iai表示一组合法的解。答案可能有很多组此时输出任意一组解即可。你需要保证 输出的0≤ai2310\le a_i2^{31}0≤ai231。你可以以任意的大小写形式输出Yes或No。例如yEsyesYes和YES都将被视为肯定的回复。输入输出样例 #1输入 #13 3 1 2 2 2 3 2 3 1 2输出 #1Yes 0 1 114514输入输出样例 #2输入 #21 1 1 1 114514输出 #2NO说明/提示考虑f(1,2)f(1,2)f(1,2)考虑路径1→21\rightarrow 21→2路径的代价为mex{0}1\text{mex}\{0\}1mex{0}1。考虑路径1→2→3→1→21\rightarrow 2\rightarrow 3\rightarrow 1\rightarrow 21→2→3→1→2路径的代价为mex{0,1,114514,0}2\text{mex}\{0,1,114514,0\}2mex{0,1,114514,0}2。考虑路径1→3→21\rightarrow 3\rightarrow 21→3→2路径的代价为mex{1,114514}0\text{mex}\{1,114514\}0mex{1,114514}0。此外还存在其他路径但可以证明不存在代价比222更大的路径故f(1,2)2f(1,2)2f(1,2)2。C实现#includebits/stdc.h#defineN100005#definelllonglong#definemodusingnamespacestd;structedge{intu,v,f;}e[N];structdsuni{intfa[N],sz[N],cnt[N];voidinit(intn){iota(fa1,fan1,1);fill(sz1,szn1,1);}intfind(intx){returnxfa[x]?x:fa[x]find(fa[x]);}intsize(intx){returnsz[find(x)];}intedge(intx){returncnt[find(x)];}voidmerge(intu,intv){ufind(u);vfind(v);cnt[u];if(uv)return;fa[v]u;sz[u]sz[v];cnt[u]cnt[v];}}dsu;vectorintvec[N];intn,m,ans[N],w[N];intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnm;dsu.init(n);for(inti1;im;i){intu,v,f;cinuvf;dsu.merge(u,v);e[i]{u,v,f};}fill(w1,wn1,-1);for(inti1;im;i){auto[u,v,f]e[i];inttdsu.find(u);if(w[t]0w[t]!f||fdsu.edge(u)){coutNo;return0;}w[t]f;vec[t].push_back(i);}for(inti1;in;i){if(vec[i].empty())continue;inttw[i];for(intj0;jvec[i].size();j)ans[vec[i][j]]j(jt);}coutYes\n;for(inti1;im;i)coutans[i] ;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容 
长河君 · 2026/10/25 1:58:27 · 阅读 1.2k 打卡信奥刷题（3648）用C++实现信奥题 P12042 [USTCPC 2025] 图上交互题 3 / Constructive Maximum Mex Path
P12042 [USTCPC 2025] 图上交互题 3 / Constructive Maximum Mex Path题目背景USTCPC 设置 3s 时限为了使得 python 通过。洛谷改为 1s 时限。2024 年 12 月 28 日 14:59:50随着最后一发 E 题的提交出现了 Wrong Answer小 G 的 EC-Final 比赛结束了。小 G 的 EC-Final 连续两年都在不同的细节题上倒闭了。克露丝卡尔酱想要帮助她的同学小 G很可惜细节题是不能批量生产的但刚好克露丝卡尔酱想到了这样一个细节题考验大家的细节题能力。希望大家不要在细节题上倒闭为什么这个系列的题目还在继续呢题目描述给定一个nnn个点mmm条边的无向图。第iii条边(ui,vi)(u_i,v_i)(ui,vi)有一个未知边权aia_iai。对于任何一条路径定义其代价如下设路径为(p0,p1,...,pk)(p_0,p_1,...,p_k)(p0,p1,...,pk)其中要求(pi−1,pi)(p_{i-1},p_i)(pi−1,pi)是无向图中的边设其为第eie_iei条边。那么路径的代价即为mexi1kaei\mathop{\text{mex}}\limits_{i1}^{k} a_{e_i}i1mexkaei。该路径可以经过重复点和重复边即ppp和eee可以包含重复的数mex\text{mex}mex是一种定义域为一个非负整数的可重集合函数值为非负整数的映射定义为集合内最小未在集合内出现过的非负整数。定义f(x,y)f(x,y)f(x,y)为从xxx到yyy的所有路径中代价的最大值。给定n,mn,mn,m再对于每条边(ui,vi)(u_i,v_i)(ui,vi)给定f(ui,vi)f(u_i,v_i)f(ui,vi)你需要求出是否存在一组合法的aia_iai如果有解你还需要构造一组解。输入格式第一行两个正整数n,mn,mn,m(1≤n,m≤105)(1\le n,m\le 10^5)(1≤n,m≤105)。第2∼m12\sim m12∼m1行每行两个正整数ui,viu_i,v_iui,vi(1≤ui,vi≤n)(1\le u_i,v_i\le n)(1≤ui,vi≤n)和一个非负整数f(ui,vi)f(u_i,v_i)f(ui,vi)(0≤f(ui,vi)231)(0\le f(u_i,v_i)2^{31})(0≤f(ui,vi)231)。请注意本题并不保证图连通可能会存在重边和自环。输出格式如果不存在解则仅输出No。否则在第一行输出Yes在第二行输出mmm个非负整数aia_iai表示一组合法的解。答案可能有很多组此时输出任意一组解即可。你需要保证 输出的0≤ai2310\le a_i2^{31}0≤ai231。你可以以任意的大小写形式输出Yes或No。例如yEsyesYes和YES都将被视为肯定的回复。输入输出样例 #1输入 #13 3 1 2 2 2 3 2 3 1 2输出 #1Yes 0 1 114514输入输出样例 #2输入 #21 1 1 1 114514输出 #2NO说明/提示考虑f(1,2)f(1,2)f(1,2)考虑路径1→21\rightarrow 21→2路径的代价为mex{0}1\text{mex}\{0\}1mex{0}1。考虑路径1→2→3→1→21\rightarrow 2\rightarrow 3\rightarrow 1\rightarrow 21→2→3→1→2路径的代价为mex{0,1,114514,0}2\text{mex}\{0,1,114514,0\}2mex{0,1,114514,0}2。考虑路径1→3→21\rightarrow 3\rightarrow 21→3→2路径的代价为mex{1,114514}0\text{mex}\{1,114514\}0mex{1,114514}0。此外还存在其他路径但可以证明不存在代价比222更大的路径故f(1,2)2f(1,2)2f(1,2)2。C实现#includebits/stdc.h#defineN100005#definelllonglong#definemodusingnamespacestd;structedge{intu,v,f;}e[N];structdsuni{intfa[N],sz[N],cnt[N];voidinit(intn){iota(fa1,fan1,1);fill(sz1,szn1,1);}intfind(intx){returnxfa[x]?x:fa[x]find(fa[x]);}intsize(intx){returnsz[find(x)];}intedge(intx){returncnt[find(x)];}voidmerge(intu,intv){ufind(u);vfind(v);cnt[u];if(uv)return;fa[v]u;sz[u]sz[v];cnt[u]cnt[v];}}dsu;vectorintvec[N];intn,m,ans[N],w[N];intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnm;dsu.init(n);for(inti1;im;i){intu,v,f;cinuvf;dsu.merge(u,v);e[i]{u,v,f};}fill(w1,wn1,-1);for(inti1;im;i){auto[u,v,f]e[i];inttdsu.find(u);if(w[t]0w[t]!f||fdsu.edge(u)){coutNo;return0;}w[t]f;vec[t].push_back(i);}for(inti1;in;i){if(vec[i].empty())continue;inttw[i];for(intj0;jvec[i].size();j)ans[vec[i][j]]j(jt);}coutYes\n;for(inti1;im;i)coutans[i] ;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容