滑雪场坐落在FJ省西北部的若干座山上。
从空中鸟瞰，滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。
你的团队负责每周定时清理雪道。你们拥有一架直升飞机，每次飞行可以从总部带一个人降落到滑雪场的某个地点，然后再飞回总部。从降落的地点出发，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。
由于每次飞行的耗费是固定的，为了最小化耗费，你想知道如何用最少的飞行次数才能完成清理雪道的任务。
BZOJ_2502_清理雪道_有源汇上下界最小流
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 150
#define M 1000050
#define S (n+1)
#define T (n+2)
#define ss (n+3)
#define tt (n+4)
#define inf 100000000
int head[N],to[M],nxt[M],flow[M],cnt=1,n,in[N];
int dep[N],Q[N],l,r;
inline void add(int u,int v,int f) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; flow[cnt]=f;
to[++cnt]=u; nxt[cnt]=head[v]; head[v]=cnt; flow[cnt]=0;
}
bool bfs() {
memset(dep,0,sizeof(dep));
dep[ss]=1;l=r=0;Q[r++]=ss;
while(l<r) {
int x=Q[l++],i;
for(i=head[x];i;i=nxt[i]) {
if(!dep[to[i]]&&flow[i]) {
dep[to[i]]=dep[x]+1;
if(to[i]==tt) return 1;
Q[r++]=to[i];
}
}
}
return 0;
}
int dfs(int x,int mf) {
if(x==tt) return mf;
int i,nf=0;
for(i=head[x];i;i=nxt[i]) {
if(dep[to[i]]==dep[x]+1&&flow[i]) {
int tmp=dfs(to[i],min(mf-nf,flow[i]));
if(!tmp) dep[to[i]]=0;
nf+=tmp;
flow[i]-=tmp;
flow[i^1]+=tmp;
if(nf==mf) break;
}
}
return nf;
}
int main() {
scanf("%d",&n);
int i,x,y;
for(i=1;i<=n;i++) {
scanf("%d",&x);
while(x--) {
scanf("%d",&y);
in[i]--; in[y]++;
add(i,y,inf);
}
}
int tmp=cnt+1;
add(T,S,inf);
for(i=1;i<=n;i++) {
add(S,i,inf);
add(i,T,inf);
if(in[i]>0) add(ss,i,in[i]);
if(in[i]<0) add(i,tt,-in[i]);
}
while(bfs()) {
while(dfs(ss,inf));
}
for(i=head[ss];i;i=nxt[i]) flow[i]=flow[i^1]=0;
for(i=head[tt];i;i=nxt[i]) flow[i]=flow[i^1]=0;
int ans=flow[tmp^1];
flow[tmp]=flow[tmp^1]=0;
add(ss,T,inf);
add(S,tt,inf);
int f;
while(bfs()) {
while((f=dfs(ss,inf))!=0) ans-=f;
}
printf("%d\n",ans);
}
原文：https://www.cnblogs.com/suika/p/9061830.html