分类 并查集 下的文章

BZOJ 1050: [HAOI2006]旅行comf

Description给你一个无向图,N(N<=500)个顶点, M(M<=5000)条边,每条边有一个权值Vi(Vi<30000)。给你两个顶点S和T,求一条路径,使得路径上最大边和最小边的比值最小。如果S和T之间没有路径,输出”IMPOSSIBLE”,否则输出这个比值,如果需要,表示成一个既约分数。 备注: 两个顶点之间可能有多条路径。Input第一行包含两个正整数,N和M。下来的M行每行包含三个正整数:x,y和v。表示景点x到景点y之间有一条双向公路,车辆必须以速度v在该公路上行驶。最后一行包含两个正整数s,t,表示想知道从景点s到景点t最大最小速度- 阅读剩余部分 -

【NOIP模拟赛】Nim 游戏·改、聚会、历史

前言又是一个模拟赛,再一次爆炸。T1 Nim 游戏·改(nim.c/cpp/pas)题目描述众所周知的 Nim 游戏是这样的:有 n 堆石子,小 A 和小 B 轮流取石子,小 A 先操作,每次选择一堆石子,在这堆中取走任意多个石子,最后没有石子可取的人输。现在为了加强Nim 游戏难度,每堆非空石子有一次额外的特殊机会,即耗掉这个机会,然后什么也不拿走,而其他条件都不变。当然,如果你将一堆本来有额外机会的石子拿空,那么这次额外机会也就没有了。现在假设小 A 和小 B 都绝顶聪明,他们将进行 T 轮游戏。每轮游戏若小 A 必胜,输出“A”,否则输出“B”。输入格式第一行为一个整- 阅读剩余部分 -

BZOJ 1015: [JSOI2008]星球大战starwar

题目描述很久以前,在一个遥远的星系,一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天,凭着一个偶然的机遇,一支反抗军摧毁了帝国的超级武器,并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。 但好景不长,很快帝国又重新造出了他的超级武器。凭借这超级武器的力量,帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁,两个星球之间的通讯通道也开始不可靠起来。现在,反抗军首领交给你一个任务:给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序,以尽量快的速度求出每一次打击之后反抗军占据的星球的连通快的个数。(如果两个星球可以通过现存的以太- 阅读剩余部分 -

【并查集】BZOJ 1370: [Baltic2003]Gang团伙

题目描述在某城市里住着n个人,任何两个认识的人不是朋友就是敌人,而且满足: 1、 我朋友的朋友是我的朋友; 2、 我敌人的敌人是我的朋友; 所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息,即某两个人是朋友,或者某两个人是敌人,请你编写一个程序,计算出这个城市最多可能有多少个团伙?输入第1行为n和m,N小于1000,M小于5000; 以下m行,每行为p x y,p的值为 E 或 F,p为 F 时,表示x和y是朋友,p为 E 时,表示x和y是敌人。输出一个整数,表示这n个人最多可能有几个团伙。样例输入64E 1 4F 3 5F 4 6E 1 2样例输出3提示{1},{- 阅读剩余部分 -