2020NYIST个人积分赛第六场 D

题意: 给n个点,m条边,让构建一个有向无环无重边的图,并且图的最短路是素数,最小生成树也是素数。 思路: 题意的可塑造性很强,我们可以让最小生成树就是最短路,呢么我们现在就是给最小生成树找一个素数,很明显最小生成树的素数范围在[1,1e14][1,1e14][1,1e14],所以预处理1-1e14不太可能,所以我们只需要找距离不小于n-1最近的素数即可,然后让最小生成树上的一条边和最小生成树上的其余为1的边组成这个素数即可 坑点: 没有注意边权w最大是1e9,我给非最小生成树上的边赋值为无穷了,一直wa 参考代码: #include #include #include #include #i