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); PRintf("%d",ans); return 0;}

上一篇：面向切面的spring

下一篇：class和struct的区别