1
10
2013
1

USACO 4.4

 1.Shuttle Puzzle
本来以为是个什么神搜索,原来是个找规律构造题。本来枚举量不算大,不过我没想到判重的好方法,不判重又怕超时,所以还是copy了题解的规律。就这样水过了。

2.Pollutant Control
求边数最少的最小割,如果有多个方案,输出边的输入顺序最小的那个。把每个边的容量Ci修改为Ci*1001+1,因为边数最大为1000,这样求出最大流tot之后tot/1001就是原图的最小割,tot mod 1001就是最小割的边数,这样同时保证了最小割有最小边数。然后按输入顺序枚举每条边,如果移除这条边(Ci)后求得的最大流totnew满足tot-totnew=Ci,则输出这条边,然后在此基础上继续枚举删边求最大流的过程。

3.Frame Up
全拓扑排序。

allTopSort(G){
    if(图G为空){
        输出缓存
        return
    }
    for(G中每个入度为零结点v){
        将v放入缓存
        从G中删除v及其出边,更新相连的结点的入度
        allTopSort(G)
        恢复v及其出边
    }
}
Category: USACO | Tags: usaco | Read Count: 883
Sons of Anarchy Hood 说:
2019年10月08日 12:44

I clearly stumbled upon your weblog and favored to mention that I’ve truely loved reading your blog posts. anyhow I’ll be subscribing in your feed and that i wish you submit once more quickly. Please keeps it top posting! thanks you a lot, I recognize your work.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com