网络流 - Page 4

「网络流24题」最长k可重区间集问题
搬运byvoid的题解「问题分析」最大权不相交路径问题，可以用最大费用最大流解决。「建模方法」方法1按左端点排序所有区间，把每个区间拆分看做两个顶点<i.a><i.b>，建立附加源S汇T，以及附加顶点S'。1、连接S到S'一条容量为K，费用为0的有向边。2、从S'到每个<i.a>连接一条容量为1，费用为0的有向边。3、从每个<i.b>到T连接一条容量为1，费用为0的有向边。4、从每个顶点<i.a>到<i.b>连...
22014年12月27日5,813费用流

「POJ1149」PIGS
DescriptionMirkoworksonapigfarmthatconsistsofMlockedpig-housesandMirkocan'tunlockanypighousebecausehedoesn'thavethekeys.Customerscometothefarmoneafteranother.Eachofthemhaskeystosomepig-housesandwantstobuyacertainnumberofpigs.AlldataconcerningcustomersplanningtovisitthefarmonthatparticulardayareavailabletoMirkoearlyinthemorningsothathecanmakeasales-planinordertomaximizethenumberofpigssold.M...
02014年12月27日5,694最大流
「泉七培训 – 杨国烨」图
「题目描述」给一张联通无向图，定义Dist[i][j]表示点i到点j之间的最短路。当前已经有了若干条的边，再给定N个A[i]，要求添加若干条无向边，使得Σ(a[i]-Dist[1][i])^2最小。输出最小的答案。「输入格式」第一行是整数N，表示节点数。接下来是N*N的矩阵，mat[i][j]=‘Y’表示i和j之间有一条无向边。保证mat[i][j]=mat[j][i]。接下来N个数，表示A[i]。「输出格式」求答案。「样例输入」4NYNNYNYNNYNYNNYN...
02014年12月26日4,249最小割
「CF498C」Array and Operations
Youhavewrittenonapieceofpaperanarrayofnpositiveintegersa[1], a[2], ..., a[n]andmgoodpairsofintegers(i1, j1), (i2, j2), ..., (im, jm).Eachgoodpair(ik, jk)meetsthefollowingconditions:ik + jkisanoddnumberand1 ≤ ik < jk ≤ n.Inoneoperationyoucanperformasequenceofactions:takeoneofthegoodpairs(ik, jk)andsomeintegerv(v > 1),whichdividesbothnumbersa[ik]anda[jk];dividebothnum...
02014年12月25日4,424最大流
「BZOJ2718 / 1143」[Violet 4] 毕业旅行
DescriptionInputOutput最多可选多少景点SampleInput76122354433667SampleOutput2HINT题解最长反链=最小路径覆盖。。。至于证明。。。百度vfk的博客floyd传递闭包后，用n-二分图最大匹配数即为答案[crayon-67405e4f9dafd999879760/] ...
02014年12月22日4,858floyd,最大流
「BZOJ1449 / 2895」[JSOI2009] 球队收益
Description在一个篮球联赛里，有n支球队，球队的支出是和他们的胜负场次有关系的，具体来说，第i支球队的赛季总支出是Ci*x^2+Di*y^2，Di<=Ci。(赢得多，给球员的奖金就多嘛)其中x,y分别表示这只球队本赛季的胜负场次。现在赛季进行到了一半，每只球队分别取得了a[i]场胜利和b[i]场失利。而接下来还有m场比赛要进行。问联盟球队的最小总支出是多少。Input第一行n，m接下来n行每行4个整数a[i],b[i],Ci,Di再接下来m行每行...
22014年12月21日4,674费用流
NOI2009植物大战僵尸
DescriptionInputOutput仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。SampleInput32100200-100-51001001211000SampleOutput25HINT在样例中,植物P1,1可以攻击位置(0,0),P2,0可以攻击位置(2,1)。一个方案为，首先进攻P1,1,P0,1，此时可以攻击P0,0。共得到能源收益为(-5)+20+10=25。注意,位置(2,1)被植物P2,0保护，所以无法攻击第2行中的任何植物。「大致数据规...
02014年12月17日6,518最小割,拓扑排序
NOI2010海拔
DescriptionYT市是一个规划良好的城市，城市被东西向和南北向的主干道划分为n×n个区域。简单起见，可以将YT市看作一个正方形，每一个区域也可看作一个正方形。从而，YT城市中包括(n+1)×(n+1)个交叉路口和2n×(n+1)条双向道路（简称道路），每条双向道路连接主干道上两个相邻的交叉路口。下图为一张YT市的地图(n=2)，城市被划分为2×2个区域，包括3×3个交叉路口和12条双向道路。小Z作为该市的市长，他根据统计信息得到...
02014年12月17日3,877STL,最小割,dijkstra
「BZOJ2893」征服王
Description虽然春希将信息传递给了雪菜，但是雪菜却好像完全不认得春希了。心急如焚的春希打开了第二世代机能，对雪菜的脑内芯片进行了直连-hack。进入到雪菜内部的春希发现（这什么玩意。。），雪菜的脑部结构被分成了n个块落，并且一些块落之间被有向边连接着。由于四分五裂的脑部，雪菜关于春希的记忆也完全消失，春希为了恋人，启动了inversionprocess.在inversionprocess中，要想使雪菜回到正常状态，需要纳米机器人的帮助。...
02014年12月16日5,283费用流,图的连通
「BZOJ3158」千钧一发
DescriptionInput第一行一个正整数N。第二行共包括N个正整数，第个正整数表示Ai。第三行共包括N个正整数，第个正整数表示Bi。Output共一行，包括一个正整数，表示在合法的选择条件下，可以获得的能量值总和的最大值。SampleInput43451298309SampleOutput39HINT1<=N<=1000,1<=Ai,Bi<=10^6题解可以证明，任意两个偶数满足2两个奇数满足1(2a+1)^2+(2b+1)^2=2(2a^2+2b^2+2a+2b+1)一定不是完全平方数所以...
12014年12月15日4,373最小割
「BZOJ1822」[JSOI2010] Frozen Nova 冷冻波
DescriptionWJJ喜欢“魔兽争霸”这个游戏。在游戏中，巫妖是一种强大的英雄，它的技能FrozenNova每次可以杀死一个小精灵。我们认为，巫妖和小精灵都可以看成是平面上的点。当巫妖和小精灵之间的直线距离不超过R，且巫妖看到小精灵的视线没有被树木阻挡（也就是说，巫妖和小精灵的连线与任何树木都没有公共点）的话，巫妖就可以瞬间杀灭一个小精灵。在森林里有N个巫妖，每个巫妖释放FrozenNova之后，都需要等待一段时间，...
62014年12月15日4,742二分法,最大流,几何
「BZOJ2929」[POI1999] 洞穴攀行
Description一队洞穴学者在ByteMountain的GrateCave里组织了一次训练。训练中，每一位洞穴学者要从最高的一个室到达最底下的一个室。他们只能向下走。一条路上每一个连续的室都要比它的前一个低。此外，每一个洞穴学者都要从最高的室出发，沿不同的路走到最低的室。问：可以有多少个人同时参加训练？任务：写一个程序：l 读入对洞穴的描述。l 计算可以同时参加训练的人数。l 将...
132014年12月9日4,124最大流