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及其出边 } }
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.