题目点击这里 当然题目难度是削弱过的。。。CTSC的题目哪只有这种难度。。。 首先题目给出的是一个有向无环图,然后求的是最长的反链长度,也就是原图里一个最大的点集,点集内部任意两点没有路径连接。 首先最长反链可以转化为最小路径覆盖问题。 对…
题目点击这里 题目很好理解就是一道最小割的题目,但是俗话说得好,“看到100就要想到网络流”。然而这道题目N和M都是1000的,所以直接上最大流算法似乎是不太可行的。 这里就要充分利用这题里面的图的特点了。 可以发现,在这个图里面: 任意两…
暑期专题三~ 这次内容有点多,所以也不是每道题都写了代码,这里都不贴出来,毕竟有的有代码有的没有有点怪怪的。。。 题目与部分题解来源于BYvoid大神,这里就不打出题目了。 部分原题没有给出数据范围,这里补充一下,以方便各位。 完结撒花~~…
在网上抄的,用来搞费用流的。 const maxn=1005; maxe=50000; var a,next,q,u,v,f,c:array[0..maxe]of longint; dis,pre,id:array[…
题目是权限题。。。 Description 有N个工作,M种机器,每种机器你可以租或者买过来. 每个工作包括若干道工序,每道工序需要某种机器来完成,你可以通过购买或租用机器来完成。 现在给出这些参数,求最大利润 这题可以用最小割来做。 首先…
感谢ZZX友情提供~ const maxe=1000000; maxn=40005; type edge=record x,y,next,op:longint; end; var e:array[0..maxe]of edg…
http://poj.org/problem?id=3469 大意就是有n个程序,有两个CPU,每个程序在不同的CPU上运行花费不同,然后有m对程序是要共享数据的,如果不在同一个CPU上运行就要有额外的花费,输出最小的花费。 一个最小割的题…
http://www.lydsy.com/JudgeOnline/problem.php?id=1412 题目大意就是将0分成1和2,然后在格子的边界建篱笆,将所有的1和2隔开,注意所有的0都要分成1和2。 解法就是用最小割的思想解决。 首…
全部加载完成