Description # lxhgww最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有2个属性，这些属性的值用[1,10000]之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。 游戏进行到最后，lxhgww遇到了终极boss，这个终极boss很奇怪，攻击他的装备所使用的属性值必须从1开始连续递增地攻击，才能对boss产生伤害。也就是说一开始的时候，lxhgww只能使用某个属性值为1的装备攻击boss，然后只能使用某个属性值为2的装备攻击boss，然后只能使用某个属性值为3的装备攻击boss……以此类推。 现在lxhgww想知道他最多能连续攻击boss多少次？
poj3310 题目链接
题意：给出一个无向图。。。问是否满足。。联通，并且无环，并且能找到一条路径，图中所有的顶点要么在这条路径上，要么与这条路径上的顶点相邻。
hdu4514
题意：给出一个无向图。。问是否有环。。。有的话输出YES。。如果没有环的话。。输出最长路径。。
hdu2874题目链接
题意：给一个森林，问两点的最短距离，或者输出两点不联通。
思路：最最重要的一点是:添加虚点！
题目链接 题意：没图不好描述，有中文题面中文题面，直接看吧。 思路：据说这道题有三种做法。 当时比赛一种都不会。
http://acm.hdu.edu.cn/showproblem.php?pid=5631 题意;给出一张n个点n+1（n<=100）条边的无向图，现在删除若干条边（至少一条边），问删完之后图依然联通的方案数。 思路：分析可知，由于只删边，不删点，n个点，最少需要n-1条边才能联通，所以最多删两条边。我们可以暴力枚举删除的两条边（或者一条边） O(n^2)的复杂度完全可以接受。剩下的问题就变成了每次删边之后判断图的连通性。 题解给出的是bfs。。。大概是bfs一遍，然后入队的点数是n就联通？ 或者dfs一遍也可以？ 也是标记过的点数是n就说明联通？ 但是看到排名考前的人都是用到了并查集来判断…比较巧妙。
http://www.lydsy.com/JudgeOnline/problem.php?id=1604 题意：了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的N(1≤N≤100000)只奶牛，你会发现她们已经结成了几个“群”．每只奶牛在吃草的时候有一个独一无二的位置坐标Xi，Yi(l≤Xi，Yi≤[1．.10^9]；Xi，Yi∈整数．当满足下列两个条件之一，两只奶牛i和j是属于同一个群的： 1．两只奶牛的曼哈顿距离不超过C(1≤C≤10^9)，即lXi - xil+IYi - Yil≤C. 2．两只奶牛有共同的邻居．即，存在一只奶牛k，使i与k，j与k均同属一个群． 给出奶牛们的位置，请计算草原上有多少个牛群，以及最大的牛群里有多少奶牛
http://poj.org/problem?id=2492
Hint
Huge input,scanf is recommended.
也是带种类的冰茶几。
由于只分了两类…我们还是可以按照上道题的做法。。
http://poj.org/problem?id=1703
种类冰茶几…看到还有一种算是拓展的交加权冰茶几？ 看到有做法是在开一个数组。。。记录是哪一组…. 但是因为只有两组….我们可以分别存… 因为不知道每一个D的两个人分别是哪个组（帮派？） 可以都存一下。 TLE了两次….应该是用了cin的事。。。改成scanf就变WA了。。。 想了下。原来是我对“not sure yet”的判断出现失误。 我开了一个v数组，记录在D下出现的人。 我误以为出现的人的帮派一定是确定的。 实际上并不是。 比如 1,3 5,7 3和7都出现了。但是3和7是一组与否显然还是“not sure yet”