图论 - Page 9 - hzwer.com

「BZOJ1370」[Baltic2003] Gang团伙
Description在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：1、我朋友的朋友是我的朋友；2、我敌人的敌人是我的朋友；所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？Input第1行为n和m，N小于1000,M小于5000；以下m行，每行为pxy，p的值为0或1，p为0时，表示x和y是朋友，p为1时，表示x和y是敌人...
22015年1月20日6,053并查集

「BZOJ3611」[HEOI2014] 大工程
题面和题解见http://www.cnblogs.com/zyfzyf/p/4231356.html[crayon-67437992e6c49507513909/]
22015年1月20日6,425虚树,dfs序,树形动规,最近公共祖先
「BZOJ2286」[SDOI2011] 消耗战
Description在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总...
22015年1月20日8,312虚树,树形动规
「CF506B」Mr. Kitayuta’s Technology
ShusekiKingdomistheworld'sleadingnationforinnovationandtechnology.Therearencitiesinthekingdom,numberedfrom1ton.ThankstoMr.Kitayuta'sresearch,ithasfinallybecomepossibletoconstructteleportationpipesbetweentwocities.Ateleportationpipewillconnecttwocitiesunidirectionally,thatis,ateleportationpipefromcityxtocityycannotbeusedtotravelfromcityytocityx.Thetransportationwithineachcityisextremelydeve...
02015年1月19日5,284并查集,图的连通
「BZOJ2654」tree
Description　　给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。题目保证有解。Input　　第一行V,E,need分别表示点数，边数和需要的白色边数。接下来E行每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。Output　　一行表示所求生成树的边权和。SampleInput22101110120SampleOutput2HINT数据规模和约定0:V<=101,2,3:V<=150,..,19:V<...
42015年1月16日7,736kruskal,二分法
「点分治练习」[hdu4812] multik
「问题描述」给定一棵n个点的树,每个点有权值Vi问是否存在一条路径使得路径上所有点的权值乘积mod(10^6+3)为K输出路径的首尾标号,若有多解,输出字典序最小的解「输入格式」第一行两个数n,K第二行n个数,表示vi接下来n-1行每行两个数x,y表示一条边「输出格式」输出两个数a,b(a<b),无解输出”Nosolution”(不含引号)。「样例输入」5602523312132425「样例输出」34「数据规模与约定」对于100%的数据,有1≤n≤10^5,0≤K≤10^6+2...
62015年1月12日6,279点分治,乘法逆元
「点分治练习」不虚就是要AK
「问题描述」czy很火，因为又有人说他虚了为了证明他不虚,他决定要在这次比赛AK现在他正在和别人玩一个游戏:在一棵树上随机取两个点(两个点可以相同)如果这两个点的距离是4的倍数,那么算czy赢,否则对方赢现在czy想知道他能获胜的概率以即约分数形式输出这个概率(即”a/b”的形式,其中a和b必须互质。如果概率为1,输出”1/1”)「输入格式」多组数据,对于每组数据第一行一个数n,表示树上的节点个数接下来n-1条边a,b,c描述a到b有一条...
52015年1月10日6,065点分治
「点分治练习」boatherds
「问题描述」询问一颗树上距离为K的点对是否存在「输入格式」第一行两个整数n,m接下来n-1条边a,b,c描述a到b有一条长度为c的路径接下来m行每行询问一个K「输出格式」对于每个K每行输出一个答案存在输出”AYE”,否则输出”NYE”(不包含引号)「样例输入」2212112「样例输出」AYENYE「数据规模与约定」对于30%的数据,有1≤n≤100对于60%的数据,有1≤n≤10^31≤m≤50对于100%的数据,有1≤n≤10^4,1≤m≤100,1≤c≤1000,1...
12015年1月10日4,047STL,点分治
「BZOJ3696」「FJ2014集训」化合物
Description 首长NOI惨跪，于是去念文化课了。现在，他面对一道化学题。这题的来源是因为在一个奇怪的学校两个化竞党在玩一个奇怪的博弈论游戏。这个游戏很蛋疼，我相信你们也没有兴趣听。由于这个游戏涉及博弈论，因此化竞的同学就要求首长求一个类似SG函数的值。他们手中有一种非常神奇的化合物，它的分子由N个原子组成（不要在意一个原子可能和及其多个原子成键这个细节）。这个分子构成一个树结构，1号分子为根。 ...
02015年1月4日4,473树形动规,最近公共祖先
「湖北省队互测day6」Asiram
2.1题目描述Asiram是个可爱的男孩子,而现在,他想给他的妹子Ecila买制作人偶的材料.这时候,他发现,在可选的n种材料之中,两种材料之间的搭配,有的会显得很漂亮,而有的就显得不那么漂亮,还有的不影响总体的美观程度.为了量化两种材料之间的搭配的漂亮程度,Asiram设置了一个“美观度”.同时,每种材料还有一定的价格,Asiram并不是想用有限的金钱去实现尽量大的美观度,而是希望他的每一分钱都能带来尽量大的美观度,即,使美观度与花费...
02015年1月4日4,043最大流
「网络流练习」defuze
连锁炸弹是恐怖分子最近开始使用的一种威力巨大的爆炸物。其复杂的结构使拆除它的难度大大增加了。一个连锁炸弹由m个引爆装置和n枚炸弹组成。每个引爆装置中有n条信号线分别与这n枚炸弹相连（1号线连接炸弹1，2号线连接炸弹2，……）。与一枚炸弹相连的m条信号线中只有一条是“安全线”——剪断后可以拆除炸弹，而剪断其它信号线则引爆炸弹。专业的技术人员将给出一个m×n的表格。其中第i行第j列显示了引爆装置i与炸弹j连接的信号线...
02015年1月4日4,528费用流
「BZOJ2756」[SCOI2012] 奇怪的游戏
DescriptionBlinker最近喜欢上一个奇怪的游戏。这个游戏在一个N*M的棋盘上玩，每个格子有一个数。每次Blinker会选择两个相邻的格子，并使这两个数都加上1。现在Blinker想知道最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同一个数则输出-1。Input输入的第一行是一个整数T，表示输入数据有T轮游戏组成。每轮游戏的第一行有两个整数N和M，分别代表棋盘的行数和列数。接下来有N行，每行M个数。Output 对于...
62015年1月3日9,068二分法,最大流