BZOJ2502 清理雪道【网络流】
Description
滑雪场坐落在FJ省西北部的若干座山上。
从空中鸟瞰，滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。
你的团队负责每周定时清理雪道。你们拥有一架直升飞机，每次飞行可以从总部带一个人降落到滑雪场的某个地点，然后再飞回总部。从降落的地点出发，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。
由于每次飞行的耗费是固定的，为了最小化耗费，你想知道如何用最少的飞行次数才能完成清理雪道的任务。
Input
Output
输出文件的第一行是一个整数k – 直升飞机的最少飞行次数。
Sample Input
8
1 3
1 7
2 4 5
1 8
1 8
0
2 6 5
0
1 3
1 7
2 4 5
1 8
1 8
0
2 6 5
0
Sample Output
4
HINT
Source
【题解】带上下界最小流，具体可以看《妈妈我终于会了最小流系列》
http://blog.csdn.net/popoqqq/article/details/48467349
# include <stdio.h>
# include <string.h>
# include <queue>
using namespace std;
const int M=1000010;
int S,T,SS,TT,head[M],c[M],next[M],to[M],flow[M],w[M],tot=1;
int n;
queue<int> q;
// remember: tot starts from 1
inline void add(int u,int v,int fl) {
++tot;
next[tot]=head[u];
head[u]=tot;
to[tot]=v;
flow[tot]=fl;
}
inline void Add(int u,int v,int fl) {
add(u,v,fl);
add(v,u,0);
}
inline void qc() {
while(!q.empty()) q.pop();
}
inline bool bfs() {
qc(); memset(c,-1,sizeof(c));
q.push(S);c[S]=1;
while(!q.empty()) {
int top=q.front(); q.pop();
for (int i=head[top];i;i=next[i]) {
int _to=to[i];
if(c[_to]>=0 || flow[i]==0) continue;
c[_to]=c[top]+1;
q.push(_to);
if(_to==T) return 1;
}
}
return 0;
}
inline int dfs(int x,int low) {
if(x==T) return low;
int fl,r=low;
for (int i=head[x];i;i=next[i]) {
int _to=to[i];
if(c[_to]!=c[x]+1 || flow[i]==0) continue;
fl=dfs(_to,min(r,flow[i]));
r-=fl;
flow[i]-=fl;
flow[i^1]+=fl;
if(!r) return low;
}
if(r==low) c[x]=-1;
return low-r;
}
inline int dinic() {
int ans=0;
while(bfs()) ans+=dfs(S,200011300);
return ans;
}
int deg[M];
int main() {
scanf("%d",&n);
S=102,SS=103,T=104,TT=105;
for (int i=1,t,tt;i<=n;++i) {
scanf("%d",&t);
for (int j=1;j<=t;++j) {
scanf("%d",&tt);
deg[i]--;
deg[tt]++;
Add(i,tt,200011300);
}
}
for (int i=1;i<=n;++i) {
if(deg[i]>0) Add(S,i,deg[i]);
if(deg[i]<0) Add(i,T,-deg[i]);
Add(SS,i,200011300);
Add(i,TT,200011300);
}
Add(TT,SS,200011300);
dinic();
int ans1=0;
for (int i=head[S];i;i=next[i])
flow[i]=flow[i^1]=0;
for (int i=head[T];i;i=next[i])
flow[i]=flow[i^1]=0;
for (int i=head[TT];i;i=next[i]) {
if(to[i]==SS) {
ans1+=flow[i^1];
flow[i]=flow[i^1]=0;
break;
}
}
Add(S,TT,200011300);
Add(SS,T,200011300);
int ans2=dinic();
printf("%d\n",ans1-ans2);
return 0;
}
评论 (0)
