分类存档：默认分类

【题目大意】给定N个矩形和N个点，如果点在矩形内则连一条边，然后求哪些边是最大匹配的必须边。

【算法分析】就是用“试删法”，如果删了最大匹配数都没变，就不是必须边，否则就是。

【其它】1A

【code】

#include

【题目大意】给定一个N*M得矩阵，#表示不可以走，0..9表示走到这上面可以得到的分数（每个点只能采集一次）一开始你在左上角，只能向下走或向右走。然后有一些地方有传送门，可以选择无耗损地从这一点传到目标点，也可以选择不传，问最多能得到多少分。

【算法分析】先缩点，然后拓扑排序，最后用dp求最长路，输出就行了。

【其它】悲剧，RE了N遍，不过又MS并非RE得问题，我一开始把不能走到的点也算到DP序列里去了，居然一直RE。。。搞不懂为什么。改了以后终于AC。

【CODE】

#include

【题目大意】给定一个无向图，让你求从其中一个点出发，经过所有边，回到这个点（边可以重复走）的最短总长度。

【算法分析】

如果是直接给欧拉图的话，就是输出边权和就可以了。

否则的话，就先floyed，然后求出任意两点的最短路。

然后给每对度为奇数的点连边，然后就是求一般无向图的最小权匹配了。

这个有经典算法的，叫带花树，不过我不会

所以，只能用状态压缩动态规划水过。

【其它】暴力47MS。。。

【程序】

#include

【题目大意】单词接龙，问能否把所有的单词接完？

【算法分析】就是先用度判断，然后看图是否连通，如果是的话，就OK。

【其它】1A。水过留痕。

6326011 edward2 1386 Accepted 168K 282MS C++ 1756B 2010-01-10 15:25:10

【程序】

#include

【题目大意】给定一个无向连通图，每次操作是在原图上加一条边，对于每次操作，输出剩下多少桥。

【算法分析】

什么是桥？就是去掉这条边以后图不再连通了。

试想一下如果缩环以后会把这个图弄成一棵树会怎样呢？

那就是树中的每条边都是割边（环上的不可能是割边）。

于是我们可以先用tarjan缩点，然后建起这颗树来。

每次如果添加边的话，那么就找那两个点对应的点的lca。

然后找lca路径上的点都缩到lca上去。

这样每条边只会常数次。所以总时间复杂度为O(E)。

【HINT】一开始SB了，想了很久，以为要把边做一下调整，后来才发现根本不用，因为树中的边肯定不可能是重边，否则那两个点都已经合成一个了。。。

【其他】居然1A，真不敢相信

纪念一下，刚好10000K内存。。。我保证，我只交了一次。。。而且没算过内存。。。

6324346 edward2 3694 Accepted 10000K 422MS C++ 2731B 2010-01-09 23:48:06

【程序】

#include