• 2017ACM萧山训练第2场(NWERC 2008)

    2017ACM萧山训练第2场(NWERC 2008)

    A:EquilibriumMobile最终天平平衡的状态下,每个结点x满足w[x]*(2^dep[x])相等统计所有的w[x]*(2^dep[x]),答案是叶子数减去出现次数最多的个数[crayon-5a2e853440ddb373604834/]B:ProvingEquivalences答案是max{入度为0的连通块个数,出度为0的连通块个数}特判连通块为1的情况每个连通块,出度0的点,向其它入度为0的连边,使得形成一个环[crayon-5a2e853440def454692007/]C:Catvs.Dog找出所有相互不兼容的人,将他们连边...

  • usaco 刷水。。。

    usaco 刷水。。。

    2017:[Usaco2009Nov]硬币游戏f(i,j)表示考虑最后i枚,前一次对手取j枚,自己的最大获益[crayon-5a2e853444602532790552/][Usaco2005Feb]RiggingtheBovineElection竞选划区爱怎么暴力怎么暴力[crayon-5a2e853444615731071877/]1661:[Usaco2006Nov]BigSquare巨大正方形狗眼瞎了wa了n发。。。枚举一条边暴力即可[crayon-5a2e853444620356461680/]1654:[Usaco2006Jan]TheCowProm奶牛舞会有向图强连通分量。。。[crayon...

  • 【bzoj1194】[HNOI2006]潘多拉的盒子

    【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,083深度搜索,图的连通
  • 【bzoj1797】[Ahoi2009]Mincut 最小割

    【bzoj1797】[Ahoi2009]Mincut 最小割

    DescriptionA,B两个国家正在交战,其中A国的物资运输网中有N个中转站,M条单向道路。设其中第i(1≤i≤M)条道路连接了vi,ui两个中转站,那么中转站vi可以通过该道路到达ui中转站,如果切断这条道路,需要代价ci。现在B国想找出一个路径切断方案,使中转站s不能到达中转站t,并且切断路径的代价之和最小。小可可一眼就看出,这是一个求最小割的问题。但爱思考的小可可并不局限于此。现在他对每条单向道路提出两个问题:问题一...

    62015年4月7日5,032最小割,图的连通
  • 【uoj #67】新年的毒瘤

    【uoj #67】新年的毒瘤

    辞旧迎新之际,喜羊羊正在打理羊村的绿化带,然后他发现了一棵长着毒瘤的树。这个长着毒瘤的树可以用n个结点m条无向边的无向图表示。这个图中有一些结点被称作是毒瘤结点,即删掉这个结点和与之相邻的边之后,这个图会变为一棵树。树也即无简单环的无向连通图。现在给你这个无向图,喜羊羊请你帮他求出所有毒瘤结点。输入格式第一行两个正整数n,m,表示有n个点m条边。保证n≥2。接下来m行,每行两个整数v,u,表示v和u之间有一条无向...

    12015年2月24日1,488图的连通
  • 【cf403C】Strictly Positive Matrix

    【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,195图的连通
  • 【cf506B】Mr. Kitayuta’s Technology

    【cf506B】Mr. Kitayuta's Technology

    ShusekiKingdomistheworld'sleadingnationforinnovationandtechnology.Therearencitiesinthekingdom,numberedfrom1ton.ThankstoMr.Kitayuta'sresearch,ithasfinallybecomepossibletoconstructteleportationpipesbetweentwocities.Ateleportationpipewillconnecttwocitiesunidirectionally,thatis,ateleportationpipefromcityxtocityycannotbeusedtotravelfromcityytocityx.Thetransportationwithineachcityisextremelydeve...

    02015年1月19日1,777并查集,图的连通
  • 【bzoj1924】[Sdoi2010]所驼门王的宝藏

    【bzoj1924】[Sdoi2010]所驼门王的宝藏

    【问题描述】==============================================================在宽广的非洲荒漠中,生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的AlpacaL.Sotomon是这个家族的领袖,外人也称其为“所驼门王”。所驼门王毕生致力于维护家族的安定与和谐,他曾亲自率军粉碎河蟹帝国主义的野蛮侵略,为族人立下赫赫战功。所驼门王一生财宝无数,但因其生性节俭低调,他将财宝埋藏在自己设计的地下宫殿里,这也是今天HenryCurt...

    02014年12月20日2,812递推与动规,STL,图的连通
  • 【bzoj2438】[中山市选2011]杀人游戏

    【bzoj2438】[中山市选2011]杀人游戏

    Description一位冷血的杀手潜入Na-wiat,并假装成平民。警察希望能在N个人里面,查出谁是杀手。警察能够对每一个人进行查证,假如查证的对象是平民,他会告诉警察,他认识的人,谁是杀手,谁是平民。假如查证的对象是杀手,杀手将会把警察干掉。现在警察掌握了每一个人认识谁。每一个人都有可能是杀手,可看作他们是杀手的概率是相同的。问:根据最优的情况,保证警察自身安全并知道谁是杀手的概率最大是多少?Input第一行有两...

    32014年12月20日2,846图的连通
  • 【图论练习】medium

    【图论练习】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,426图的连通
  • 【图论练习】easy

    【图论练习】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,572图的连通
  • 【bzoj2893】征服王

    【bzoj2893】征服王

    Description虽然春希将信息传递给了雪菜,但是雪菜却好像完全不认得春希了。心急如焚的春希打开了第二世代机能,对雪菜的脑内芯片进行了直连-hack。进入到雪菜内部的春希发现(这什么玩意。。),雪菜的脑部结构被分成了n个块落,并且一些块落之间被有向边连接着。由于四分五裂的脑部,雪菜关于春希的记忆也完全消失,春希为了恋人,启动了inversionprocess.在inversionprocess中,要想使雪菜回到正常状态,需要纳米机器人的帮助。...

    02014年12月16日2,023费用流,图的连通
  • 【bzoj2427】[HAOI2010]软件安装

     【bzoj2427】[HAOI2010]软件安装

    Description现在我们的手头有N个软件,对于一个软件i,它要占用Wi的磁盘空间,它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上,使得这些软件的价值尽可能大(即Vi的和最大)。但是现在有个问题:软件之间存在依赖关系,即软件i只有在安装了软件j(包括软件j的直接或间接依赖)的情况下才能正确工作(软件i依赖软件j)。幸运的是,一个软件最多依赖另外一个软件。如果一个软件不能正常工作,那么它能够...

    42014年12月13日3,002树形动规,图的连通
1 / 3 1 2 3 下一页 »