题目：https://www.luogu.org/problemnew/show/P1522 懒于仔细分情况而直接像题解那样写floyd然后不明白最后一步max的含义了... 分开考虑怎么保证在一个内呢？如果新连边的min与原直径的max在三个连通块里怎么办？ 代码如下： #inclu…

挺简单一个题&#xff0c;可惜当时没想到&#xff0c;有点巧妙丫&#xff01; #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #define maxn 255 using namespace std; char list[maxn][maxn]; do…

题目传送门&#xff1a;https://www.luogu.org/problemnew/show/P1522 题意&#xff1a; 给出n个坐标&#xff0c;以及他们的连通情况&#xff0c;你可以再选任意两个点相连&#xff0c;求此时的最小的直径&#xff08;图的直径&#xff1a;图中最远两点的距离&#xff09;。 …

这题是一个匹配问题&#xff0c;一开始想用km做最佳匹配&#xff0c;但是图很大肯定会tle&#xff0c;思考无果后只能去搜搜题解&#xff0c;这是个经典问题吧。从http://www.cnblogs.com/drizzlecrj/archive/2008/09/12/1290176.html这里找到了相应的资料。 稳定婚姻是组合数学…

这题挺好……有几个坑……&#xff08;反正我都跳进去了&#xff09; 对于新的更大的图&#xff0c;由于求的是最小连接边&#xff0c;所以它的值可能小于之前单独一个图的最长的最短路…… 所以之后的值应该取个max&#xff08;emmm……&#xff09; 所以第一次我只拿了70。。…

Description 有一个由n台计算机组成的无线网络。(n < 1001),正常情况下&#xff0c;每台计算机都能跟与它距离不超过d的任何计算机通讯(d < 20000)。地震发生了。所有的计算机都陷入瘫痪。专家们试着一台一台地修复计算机&#xff0c;以恢复整个无线网络。有时在修复的过…

题目大意&#xff1a; 题目链接&#xff1a; USACO:http://train.usaco.org/usacoprob2?aTyEfGmq7aAo&Scowtour 洛谷&#xff1a;https://www.luogu.org/problemnew/show/P1522 有一个无向图&#xff0c;可以在两个不同的联通块中选择其中两个结点并连接&#xff0c;求此…

题目&#xff1a;牛的旅行 思路&#xff1a; 先预处理出两点间的距离&#xff0c;跑一边floyd&#xff0c;然后处理出每个点到离它最远的和它连通的距离L[i]。 然后再对于每个点&#xff0c;枚举所有和它不连通的点j&#xff0c;用L[i]L[j]d(i,j)更新最小答案。 注意下&#x…