bzoj 2502: 清理雪道有源匯最小流

2019-11-06 06:08:47

字體：大中小

來源：轉載

供稿：網友

題意

滑雪場坐落在FJ省西北部的若干座山上。從空中鳥瞰，滑雪場可以看作一個有向無環圖，每條弧代表一個斜坡（即雪道），弧的方向代表斜坡下降的方向。你的團隊負責每周定時清理雪道。你們擁有一架直升飛機，每次飛行可以從總部帶一個人降落到滑雪場的某個地點，然后再飛回總部。從降落的地點出發，這個人可以順著斜坡向下滑行，并清理他所經過的雪道。由于每次飛行的耗費是固定的，為了最小化耗費，你想知道如何用最少的飛行次數才能完成清理雪道的任務。 n<=100

分析

有上下界網絡流處女題。。。顯然是每條邊的下界均為1上界均為inf，然后跑最小流即可。最小流：建立超級源ss和超級匯tt，先跑一遍可行流，設其為sum，然后把ss有關的邊和與tt有關的邊還有t到s的連邊都刪掉，然后連接ss?>t $ss->t$ 和s?>tt $s->tt$ ，跑一遍最大流，設為ans，那么答案即為sum-ans. 這是因為流完可行流之后原圖中會有一些多出來的流，那么就要盡量的退流。

代碼

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#include<queue>#define N 225#define inf 0x3f3f3f3fusing namespace std;int n,cnt,s,t,ss,tt,last[N],dis[N],d[N],ans;struct edge{int to,c,next;}e[N*N*5];queue <int> q;void addedge(int u,int v,int c){ e[++cnt].to=v;e[cnt].c=c;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].c=0;e[cnt].next=last[v];last[v]=cnt;}bool bfs(){ memset(dis,0,sizeof(dis)); dis[ss]=1; while (!q.empty()) q.pop(); q.push(ss); while (!q.empty()) { int u=q.front(); q.pop(); for (int i=last[u];i;i=e[i].next) if (e[i].c&&!dis[e[i].to]) { dis[e[i].to]=dis[u]+1; if (e[i].to==tt) return 1; q.push(e[i].to); } } return 0;}int dfs(int x,int maxf){ if (x==tt||!maxf) return maxf; int ret=0; for (int i=last[x];i;i=e[i].next) if (e[i].c&&dis[e[i].to]==dis[x]+1) { int f=dfs(e[i].to,min(maxf-ret,e[i].c)); e[i].c-=f; e[i^1].c+=f; ret+=f; if (ret==maxf) break; } return ret;}int main(){ scanf("%d",&n); cnt=1; for (int i=1;i<=n;i++) { int x,y; scanf("%d",&x); for (int j=1;j<=x;j++) { scanf("%d",&y); d[i]--;d[y]++; addedge(i,y,inf); } } s=n+1;t=s+1; ss=t+1;tt=ss+1; for (int i=1;i<=n;i++) { addedge(s,i,inf);addedge(i,t,inf); if (d[i]>0) addedge(ss,i,d[i]); else if (d[i]<0) addedge(i,tt,-d[i]); } addedge(t,s,inf); while (bfs()) dfs(ss,inf); ans=e[cnt].c; e[cnt].c=e[cnt^1].c=0; for (int i=last[ss];i;i=e[i].next) e[i].c=e[i^1].c=0; for (int i=last[tt];i;i=e[i].next) e[i].c=e[i^1].c=0; addedge(ss,t,inf);addedge(s,tt,inf); while (bfs()) ans-=dfs(ss,inf);