首先双连通缩点建立新图（顺带求原图的总的桥数，事实上因为原图是一个强连通图，所以桥就等于缩点后的边）此时得到的图类似树结构，对于新图求一次直径，也就是最长链。我们新建的边就一定是连接这条最长链的首尾，这样就将原图的桥降低了直径个。#include<iostream>#include<cstring&g...

很好的一道图论题，整整撸了一上午。。。题意是给定一个无向图，要求将所有边变为有向边，求最少加入多少条有向边，使得该图强连通？这里先假设一个问题：给定一个无向子图，该子图具有怎样的性质才能使得将其无向边都变为有向边后强连通？显然是边-双连通！边连通的性质就是任意两点间存在边部重合的两条路，所以你懂的。。。所以这个题的解法...

　　有一个有向图，每一个节点有一个权值，其中有一些结束点。　　现在，你要从S出发，到达任意一个结束点，使得经过的节点的权值和最大（可以重复经过某一个节点，但是权值只记入一次）。 　　小码农题。　　如果有强连通分量，那么之间的点是可以全部拿到的，傻子才不拿。　　所以先Tarjan强连通缩个点。　　然后就是一个D...

 　　有n只牛，有m个羡慕关系。　　羡慕关系具有传递性。　　如果A羡慕B，B羡慕C，那么我们认为A也羡慕C。　　问有多少牛被所有其他牛羡慕。 　　这次做这题我已经是第三遍了。　　USACO经典老题啊！（奶牛）　　POJ上面也有，叫popularcow。　　做法：　　先Tarjan强连通缩个点。　　然...

原文链接https://www.cnblogs.com/zhouzhendong/p/9258043.html　　给定一个有向图，有$n$个节点$m$条边，边权值$in[0,1000]$。　　小明要从$1$走到$n$，要求路径长度最大为$d+k$，其中$d$为$1$到$n$最短路长度。　　问小明有多少种走法，答案对$p...