20171012 图论test3

考试策略

看完题目,T1和T2是做过的题,T4有60分是最短路计数,但是好像改一改就可以过?T3暂时没有思路。于是我就先快速打了T1和T2,然后想出了T4的解法,写了T4,再后来发现T3有30分是裸的最小生成树,再想了想写了个骗分一般的程序......结果A了??(然而是因为数据水)

T1

期望得分:100 实际得分:100

题目描述:poj2186

题目分析:tarjan缩点,然后如果入度为0的点只有一个,输出那个强连通分量的大小,否则输出0.


代码


T2

期望得分:100 实际得分:100

题目描述:HDU1598

题目分析:把边权从小到大排序,枚举边权最小的边,然后往后处理所有边。对于每一条边,将此边相连的两个点加入同一个并查集,当s和t属于同一个并查集

代码



T3

期望得分:30 实际得分:100(然而是因为数据水)

题目描述:poj1639

题目分析

我......我不会度限制生成树......我......我在最小生成树的时候判断如果和公园相连的边已经选了k条,就不选和公园相连的边了......我......我A了这题......

好吧,说一说正解。

应该看得出题目是一个Park度数小于等于k的最小生成树吧?

首先,我们去掉所有与Park相连的边,假设图被分成了m块,那么就弄m个最小生成树出来。再选m条最小的边让m块与Park相连,这个时候我们得到了Park的最小度生成树。

然后我们添加新的与Park相连的边。每次dfs一遍生成树,记录Park到每一个点的路径上的最长的那一条(当然不能是与Park相连的某一条),然后就可以算出添加一条新的与Park相连的边可以使当前答案减小的最大值,去掉该去的边,加上该加的边,重复此过程,直到与Park相连的边为k条或是不能使得答案减小为止。

代码



T4

期望得分:100 实际得分:100

题目描述:poj3463

题目分析-方法1

首先在反向图上从t开始跑一遍spfa,得到每一个点到终点的最短路。然后记忆化搜索,f[x]表示从x到t的最短路数量,g[x]表示从x到t的比最短路长1的路的数量,状态转移看代码吧。

代码



题目分析-方法2**:

呃,所以为什么其他人都是在dijkstra的时候顺便求次短路和计数呐?