这是一些CF上的simple??的图论题。QAQ
CF208C。给定一个有$n$个节点的无向图。选一个点成为特殊点,与特殊点相连的边称之为特殊边。求,对于所有$1 \rightarrow n$的最短路,经过的特殊边数量的平均值,的最大值。$n<=100, m<=n(n-1)/2$
最短路,拓扑图的DP。考虑到有两种情况,一种是$1$或$n$成为了特殊点,此时答案一定为$1$。否则我们可以求出经过每个点的最短路条数,即可。在BFS之后,按照距离来排序就完成了拓扑排序。
CF154C。有编号为$[1,n]$的$n$个人,并给一些相识关系。对于两个人$(i, j)$有,对所有剩下的人,$k$要么与$i,j$相识,$k$要么与$i,j$不相识,求这样的$(i,j)$有多少对。
图上的HASH。考虑到我们可以将点连出去的边进行$Hash$,如果两个点的$Hash$值相同,则这一对点满足条件。还存在着一个问题,就是说,如果$(i,j)$本身存在连边,他们的$Hash$值不同,于是它们可以把自己加入各自的$Hash$。由于这个$Hash$函数要求与顺序无关,所以我们可以对每个点赋予一个值,然后加起来或者异或,即可。