一道很经典的费用流题目,也是第一次写费用流.SPFA写错了一点.另外终于理解上次SGU那道题为啥可以用费用流了…
题目描述懒得写了…建图的方法:s到每个盒子连边,容量为盒子里球的数量,费用0.盒子到t连边,容量为1,费用0.相邻的两个盒子连边,容量为正无穷,费用1.要求的就是最小费用.
{ SPOJ 371; BOXES - sqybi’s code - 最小费用最大流}//for my winstyprogram boxes_sqybi; const nn = 1000; inf = 100000000; mm = nn * 4; tt = nn + 2;
var cases, times, n, m, s, t, i, x, y, qs, ql, temp, now, res: longint; head, dist, go, path, pathEdge: array[1..tt]of longint; q: […]
这道题很神奇…好久没做这么神奇的题目了.
首先对于两个数a,b,如果可以解出的话,一定可以用如下方法解决(一定在500步以内):首先定义minP(x)为x除了1以外最小的因数.如果a是奇数,那么a’<-a+minP(a);如果b是奇数,那么b’<-b-minP(b).这样a和b就都成了偶数.然后假设每次存在最大的k使得a’+2^k<b’,那么让a’<-a’+2^k,直到a’=b’为止.这样就找到了一个解(a, a’, a”, a”’, …, b’, b).
挺神奇的…
{ SGU 330; Numbers - sqybi’s code}//for my winstyprogram sgu330_sqybi; var da, db: double; a, b, pa, pb, t, r: int64; i, l: longint; path: array[1..500]of int64;
begin readln(a, b); if a = 2 then begin writeln(’Impossible’); halt; end; da := a; db := b; pa := 0; […]
Liked it here?
Why not try sites on the blogroll...