滑雪場坐落在FJ省西北部的若干座山上。 從空中鳥瞰，滑雪場可以看作一個有向無環(huán)圖，每條弧代表一個斜坡（即雪道），弧的方向代表斜坡下降的方向。 你的團隊負責(zé)每周定時清理雪道。你們擁有一架直升飛機，每次飛行可以從總部帶一個人降落到滑雪場的某個地點，然后再飛回總部。從降落的地點出發(fā)，這個人可以順著斜坡向下滑行，并清理他所經(jīng)過的雪道。 由于每次飛行的耗費是固定的，為了最小化耗費，你想知道如何用最少的飛行次數(shù)才能完成清理雪道的任務(wù)。 　　題意就是給定一張DAG，求每條邊起碼經(jīng)過一次求覆蓋所有邊的最小路徑條數(shù) 如圖 　　這時的答案為4
　　很容易看出，就是在每條邊都經(jīng)過一次的情況下求一次最小流 　　即帶有下界的最小流 　　解決方法很簡單： 　　對于一條(x,y) 　　從x到y(tǒng)連一條容量為1，費用為-INF的邊，根據(jù)最小費用最大流的性質(zhì) 　　我們可以看出顯然這條邊是會流到的 　　然后鑒于每條邊經(jīng)過的次數(shù)不止一次，所以從x到y(tǒng)再連一條容量為INF，費用為0的邊 　　源點向所有入度為0的點連邊，所有出度為0的邊向匯點連邊 　　但是顯然求最大流是求不完的，什么時候停止呢？ 　　每次增廣必定增廣出的是費用最小的一條路徑 　　當(dāng)圖中還有邊未經(jīng)過的時候，增光出來的路徑中畢竟有費用為-INF的邊 　　當(dāng)圖中所有的邊都經(jīng)過的時候，增廣出的路徑費用為0 　　這個時候就可以停止了 　　 　　另外事后考慮了一個問題： 　　這樣做為什么能保證是最小流呢？ 　　每次增廣然后標(biāo)記感覺只是模擬 　　但是會發(fā)現(xiàn)，每條未經(jīng)過的邊權(quán)值為-INF，和最小費用最大流結(jié)合 　　保證每次選出的路徑能盡量多填滿一些邊 　　反向弧的存在又使結(jié)果的正確性有了更多重的保證 program xjt7; const maxn = 110;maxm = 100010;INF = 10000000007; var n,m,e,s,t,x,y:int64;i,j:longint;fa,next,link,w,cost,rec,son:array[-1..maxm]of int64;dis,opt,pos,pre,b,lea:array[-1..maxn]of int64;vis:array[-1..maxn]of boolean;function min(a,b:int64):int64; beginif a<b then exit(a) else exit(b); end;procedure add(x,y,z,cst:int64); begininc(e);fa[e]:=y;next[e]:=link[x];link[x]:=e;w[e]:=z;cost[e]:=cst;rec[e]:=e+1;son[e]:=x;inc(e);fa[e]:=x;next[e]:=link[y];link[y]:=e;w[e]:=0;cost[e]:=-cst;rec[e]:=e-1;son[e]:=y; end;function spfa:boolean; var head,tail,x,j:int64; beginfillchar(vis,sizeof(vis),true);fillchar(dis,sizeof(dis),63);head:=0;tail:=1;opt[1]:=s;dis[s]:=0;vis[s]:=false;while head<>tail dobeginhead:=(head+1) mod maxn;x:=opt[head];j:=link[x];while j<>0 dobeginif (w[j]>0)and(dis[x]+cost[j]<dis[fa[j]]) thenbegindis[fa[j]]:=dis[x]+cost[j];pre[fa[j]]:=j;if vis[fa[j]] thenbeginvis[fa[j]]:=false;tail:=(tail+1) mod maxn;opt[tail]:=fa[j];end;end;j:=next[j];end;vis[x]:=true;end;if dis[t]<>dis[t+1] then exit(true);exit(false); end;procedure MCMF; var sum,u,mn,ans:int64; beginans:=0;while spfa dobeginsum:=0;u:=t;mn:=INF;while u<>s dobeginmn:=min(mn,w[pre[u]]);u:=son[pre[u]];end;u:=t;while u<>s dobegininc(sum,mn*cost[pre[u]]);dec(w[pre[u]],mn);inc(w[rec[pre[u]]],mn);u:=son[pre[u]];end;if sum>0 then break;inc(ans,mn);end;writeln(ans); end;begin//assign(input,'xjt7.in');reset(input); readln(n);fillchar(b,sizeof(b),0);for i:=1 to n dobeginread(lea[i]);for j:=1 to lea[i] dobeginread(y);add(i,y,1,-INF);add(i,y,INF,0);inc(b[y]);end;readln;end;s:=0;t:=n+1;for i:=1 to n do if b[i]=0 then add(s,i,INF,1);for i:=1 to n do if lea[i]=0 then add(i,t,INF,1);MCMF; end.

?

轉(zhuǎn)載于:https://www.cnblogs.com/mjy0724/p/4463023.html

總結(jié)

以上是生活随笔為你收集整理的[BZOJ2502]清理雪道解题报告|带下界的最小流的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。