P1477 [NOI2008] 假面舞会 题解
water_tomato·2021-08-19·991 次阅读
发现题解区说大多都是直接说再连一条边权为 $-1$ 的边,在这里略微证明一下正确性. 
首先发现若图中没有环,最大答案为所有联通块的最长链长度之和,最小答案为 $3$.
若存在环,则最大答案为所有环的 $\gcd$  .为了在可接受的时间内找到所有环,我们对于每一条边的 $u\rightarrow v$  ,从 $u$   向 $v$   连一条边权为 $1$   的边,从 $v$   向 $u$   连一条边权为 $-1$   的边.然后每一次都从任意一个未被搜索过的点开始搜,并记录每一个点的距离 $di