Beyond the Void

这是NOI2007最简单的一道题了吧，考察的是细心。由于要求每对顶点的最短路径，可以用floyd求。定义path[i][j]为从i到j的最短路径的条数，floyd松弛时，要更新path[i][j] = path[i][k] * path[k][j]，如果遇到dist[i][k] + dist[k][j] == dist[i][j]这样的情况，要令path[i][j] += path[i][k] * path[k][j]。

接下来就是根据定义求每个顶点重要程度值I了，其中C(s,t)=path[s][t]，根据乘法原理，过v的最短路径条数C(s,t,v)=path[s][v] * path[v][t]。求出I值输出即可。注意最短路径数目不超过10^10，所以要用到64位整型数来记录路径条数。

Read the rest of this entry »

题目要求是删除权值之和最少的一些边，使得从1到N的最短路径变大。方法是求最短路径网络上的最小割集。首先求出从1到N的最短路径网络，方法是分别从1和N求单源最短路径，然后枚举每条边，如果边(a,b)满足dis(1,a) + w(a,b) + dis(b,N) = dis(1,N) ，则(a,b)是最短路径网络上的(有向)边。

接下来求从1到N的网络最大流，即可求出最小割集。由于是求任意一个最小割集，所以只需遍历一边残余网络，S集合与T集合之间的边，就是一个最小割集。
Read the rest of this entry »

这道题道德解法是离散化+染色+BFS最短路径。首先，由于坐标范围很大，离散化处理是很有必要的，这样可以把坐标范围从10000压缩到210以内。在离散化以后的格子中进行一次Floodfill，对每个封闭区域进行染色处理。接下来，把每个染色区域看成图中的一个顶点，相邻的染色区域建立一条权值为1的无向边。最后，求S到T所在染色区域对应顶点之间的最短路径，由于边权全部为1，只需一边BFS即可。

这道题是大名鼎鼎的《骗分导论》上的一道例题，除了骗分以外，这种解法也是非常好的。
Read the rest of this entry »

前两问是最短路，第三问是标准的次短路径。求法是先求出最短路径，然后枚举每条从S到T的最短路径上的边，删除以后再求一次最短路径，保留最小值就是次短路径。
Read the rest of this entry »

这道题不同于一般的次短路径问题，因为允许边重走。看似更为复杂了，其实是更简单了一些。方法为先用Heap+Dijkstra求出1和N的单源最短路径，把无向边看成两个有向边，然后枚举每单向条边(u,v)，计算Dist=dis(1,u) + dis(N,v)，看看此时Dist的值是否大于dis(1,N)，如果是的话用它更新次短路径，保留一个最小的值。

USACO 2006 November Gold

Read the rest of this entry »