P6004 [USACO20JAN] Wormhole Sort S题目描述Farmer John 的奶牛们已经厌倦了他对她们每天早上排好序离开牛棚的要求。她们刚刚完成了量子物理学的博士学位准备将这一过程搞快点。今天早上如同往常一样Farmer John 的NNN头编号为1…N1 \ldots N1…N的奶牛1≤N≤1051 \leq N \leq 10^51≤N≤105分散在牛棚中NNN个编号为1…N1 \ldots N1…N的不同位置奶牛iii位于位置pip_ipi​。但是今天早上还出现了MMM个编号为1…M1 \ldots M1…M的虫洞1≤M≤1051 \leq M \leq 10^51≤M≤105其中虫洞iii双向连接了位置aia_iai​和bib_ibi​宽度为wiw_iwi​1≤ai,bi≤N,ai≠bi,1≤wi≤1091\le a_i,b_i\le N, a_i\neq b_i, 1\le w_i\le 10^91≤ai​,bi​≤N,ai​bi​,1≤wi​≤109。在任何时刻两头位于一个虫洞两端的奶牛可以选择通过虫洞交换位置。奶牛们需要反复进行这样的交换直到对于1≤i≤N1 \leq i \leq N1≤i≤N奶牛iii位于位置iii。奶牛们不想被虫洞挤坏。帮助她们最大化被她们用来排序的虫洞宽度的最小值。保证奶牛们有可能排好序。输入格式输入的第一行包含两个整数NNN和MMM。第二行包含NNN个整数p1,p2,…,pNp_1,p_2,\ldots ,p_Np1​,p2​,…,pN​。保证ppp是1…N1 \ldots N1…N的一个排列。对于111到MMM之间的每一个iii第i2i2i2行包含整数ai,bi,wia_i,b_i,w_iai​,bi​,wi​。输出格式输出一个整数为在排序过程中奶牛必须挤进的虫洞的最小宽度的最大值。如果奶牛们不需要用任何虫洞来排序输出−1-1−1。输入输出样例 #1输入 #14 4 3 2 1 4 1 2 9 1 3 7 2 3 10 2 4 3输出 #19输入输出样例 #2输入 #24 1 1 2 3 4 4 2 13输出 #2-1说明/提示样例解释 1以下是一个仅用宽度至少为 9 的虫洞给奶牛排序的可能方案奶牛 1 和奶牛 2 使用第三个虫洞交换位置。奶牛 1 和奶牛 3 使用第一个虫洞交换位置。奶牛 2 和奶牛 3 使用第三个虫洞交换位置。子任务测试点3∼53 \sim 53∼5满足N,M≤1000N,M \leq 1000N,M≤1000。测试点6∼106 \sim 106∼10没有额外限制。C实现#includebits/stdc.h#defineintlonglong#definemaxn100020usingnamespacestd;intf[maxn];intn,m,arr[maxn];//arr 表示奶牛最初的位置structdong{inta,b,w;//a b 为连接的两个节点w 为宽度};dong h[maxn];intfind(intx){if(f[x]x)returnx;returnf[x]find(f[x]);}//并查集之 findvoidinit(){for(inti1;in;i)f[i]i;}//初始化每个节点最初的“根”是自己boolcmp(dong x,dong y){returnx.wy.w;}signedmain(){cinnm;for(inti1;in;i)cinarr[i];for(inti1;im;i)cinh[i].ah[i].bh[i].w;intans-1;sort(h1,h1m,cmp);intcnt0,xx,yy;init();//读入排序初始化for(inti1;im;i){while(find(cnt)find(arr[cnt])){cnt;if(cntn){coutans;return0;}}xxfind(h[i].a);yyfind(h[i].b);if(xx!yy){f[xx]yy;ansh[i].w;}}coutans;//输出return0;//完结撒花}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容