图的连通 - hzwer.com

2017ACM萧山训练第2场(NWERC 2008)
A:EquilibriumMobile最终天平平衡的状态下，每个结点x满足w[x]*(2^dep[x])相等统计所有的w[x]*(2^dep[x])，答案是叶子数减去出现次数最多的个数[crayon-5b0ab7e6ace4a158040449/]B:ProvingEquivalences答案是max{入度为0的连通块个数，出度为0的连通块个数}特判连通块为1的情况每个连通块，出度0的点，向其它入度为0的连边，使得形成一个环[crayon-5b0ab7e6ace5f587751183/]C:Catvs.Dog找出所有相互不兼容的人，将他们连边...
12017年8月8日2,265递推与动规,贪心,单调队列,图的连通,二分图匹配,扩展欧几里得算法

usaco 刷水。。。
2017:[Usaco2009Nov]硬币游戏f(i,j)表示考虑最后i枚，前一次对手取j枚，自己的最大获益[crayon-5b0ab7e6ae692931789255/][Usaco2005Feb]RiggingtheBovineElection竞选划区爱怎么暴力怎么暴力[crayon-5b0ab7e6ae6a3697456656/]1661:[Usaco2006Nov]BigSquare巨大正方形狗眼瞎了wa了n发。。。枚举一条边暴力即可[crayon-5b0ab7e6ae6af313622018/]1654:[Usaco2006Jan]TheCowProm奶牛舞会有向图强连通分量。。。[crayon...
02015年5月26日1,988递推与动规,深度搜索,图的连通
「BZOJ1194」[HNOI2006] 潘多拉的盒子
DescriptionInput第一行是一个正整数S，表示宝盒上咒语机的个数，（1≤S≤50）。文件以下分为S块，每一块描述一个咒语机，按照咒语机0,咒语机1„„咒语机S－1的顺序描述。每一块的格式如下。一块的第一行有两个正整数n,m。分别表示该咒语机中元件的个数、咒语源输出元的个数（1≤m≤n≤50）。接下来一行有m个数，表示m个咒语源输出元的标号（都在0到n-1之间）。接下来有n行，每一行两个数。第i行（0≤i≤n-1）的两个数表示pi...
02015年4月28日2,489深度搜索,图的连通
「BZOJ1797」[Ahoi2009] Mincut 最小割
DescriptionA,B两个国家正在交战，其中A国的物资运输网中有N个中转站，M条单向道路。设其中第i(1≤i≤M)条道路连接了vi,ui两个中转站，那么中转站vi可以通过该道路到达ui中转站，如果切断这条道路，需要代价ci。现在B国想找出一个路径切断方案，使中转站s不能到达中转站t，并且切断路径的代价之和最小。小可可一眼就看出，这是一个求最小割的问题。但爱思考的小可可并不局限于此。现在他对每条单向道路提出两个问题：问题一...
62015年4月7日6,348最小割,图的连通
「uoj #67」新年的毒瘤
辞旧迎新之际，喜羊羊正在打理羊村的绿化带，然后他发现了一棵长着毒瘤的树。这个长着毒瘤的树可以用n个结点m条无向边的无向图表示。这个图中有一些结点被称作是毒瘤结点，即删掉这个结点和与之相邻的边之后，这个图会变为一棵树。树也即无简单环的无向连通图。现在给你这个无向图，喜羊羊请你帮他求出所有毒瘤结点。输入格式第一行两个正整数n,m，表示有n个点m条边。保证n≥2。接下来m行，每行两个整数v,u，表示v和u之间有一条无向...
12015年2月24日1,749图的连通
「CF403C」Strictly Positive Matrix
Youhavematrixaofsizen × n.Let'snumbertherowsofthematrixfrom1tonfromtoptobottom,let'snumberthecolumnsfrom1tonfromlefttoright.Let'suseaijtorepresenttheelementontheintersectionofthei-throwandthej-thcolumn.Matrixameetsthefollowingtwoconditions:foranynumbersi, j(1 ≤ i, j ≤ n)thefollowinginequalityholds:aij ≥ 0;.Matrixbisstrictlypositive,ifforanynumbersi, j(1 ≤ i, j ≤ n)theine...
02015年1月24日1,484图的连通
「CF506B」Mr. Kitayuta’s Technology
ShusekiKingdomistheworld'sleadingnationforinnovationandtechnology.Therearencitiesinthekingdom,numberedfrom1ton.ThankstoMr.Kitayuta'sresearch,ithasfinallybecomepossibletoconstructteleportationpipesbetweentwocities.Ateleportationpipewillconnecttwocitiesunidirectionally,thatis,ateleportationpipefromcityxtocityycannotbeusedtotravelfromcityytocityx.Thetransportationwithineachcityisextremelydeve...
02015年1月19日2,144并查集,图的连通
「BZOJ1924」[SDOI2010] 所驼门王的宝藏
「问题描述」==============================================================在宽广的非洲荒漠中,生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的AlpacaL.Sotomon是这个家族的领袖,外人也称其为“所驼门王”。所驼门王毕生致力于维护家族的安定与和谐,他曾亲自率军粉碎河蟹帝国主义的野蛮侵略,为族人立下赫赫战功。所驼门王一生财宝无数,但因其生性节俭低调,他将财宝埋藏在自己设计的地下宫殿里,这也是今天HenryCurt...
02014年12月20日3,543递推与动规,STL,图的连通
「BZOJ2438」[中山市选2011] 杀人游戏
Description一位冷血的杀手潜入Na-wiat，并假装成平民。警察希望能在N个人里面，查出谁是杀手。警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他认识的人，谁是杀手，谁是平民。假如查证的对象是杀手，杀手将会把警察干掉。现在警察掌握了每一个人认识谁。每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。问：根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多少？Input第一行有两...
32014年12月20日3,360图的连通
「图论练习」medium
hzwer蒟蒻刚刚学了点图论，现在他面对一张无向连通图他想问你最少添加多少条边，使得任意两点之间有两条无公共边的路（可以有公共点）输入格式第一行n，m，n个点m条边接下来m行，每行u，v表示u到v之间有一条无向边（可能重复描述一条边）输出格式一行，答案样例输入551223344545样例输出1 数据范围20%的数据N<=20,M<=5040%的数据N<=2000,M<=200070%的数据N<=20000,M<=20000100%的数据N&...
42014年12月20日1,659图的连通
「图论练习」easy
hzwer蒟蒻刚刚学了点图论，现在他面对一张有向图他想问你：1：最少选择多少个点，使得从这些点出发能遍历完整个图2：最少添加多少条有向边，能使得整个图成为强连通图输入格式第一行n，m，n个点m条边接下来m行，每行u，v表示一条u到v的有向边输出格式两行，分别为两问答案样例输入53122334样例输出22 数据范围20%的数据N<=20,M<=5040%的数据N<=2000,M<=2000070%的数据N<=5000,M<=5000010...
12014年12月20日1,925图的连通
「BZOJ2893」征服王
Description虽然春希将信息传递给了雪菜，但是雪菜却好像完全不认得春希了。心急如焚的春希打开了第二世代机能，对雪菜的脑内芯片进行了直连-hack。进入到雪菜内部的春希发现（这什么玩意。。），雪菜的脑部结构被分成了n个块落，并且一些块落之间被有向边连接着。由于四分五裂的脑部，雪菜关于春希的记忆也完全消失，春希为了恋人，启动了inversionprocess.在inversionprocess中，要想使雪菜回到正常状态，需要纳米机器人的帮助。...
02014年12月16日2,585费用流,图的连通