首页 > 代码库 > bzoj 2502: 清理雪道 最小流
bzoj 2502: 清理雪道 最小流
2502: 清理雪道
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 868 Solved: 466
[Submit][Status][Discuss]
Description
滑雪场坐落在FJ省西北部的若干座山上。
从空中鸟瞰，滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。
你的团队负责每周定时清理雪道。你们拥有一架直升飞机，每次飞行可以从总部带一个人降落到滑雪场的某个地点，然后再飞回总部。从降落的地点出发，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。
由于每次飞行的耗费是固定的，为了最小化耗费，你想知道如何用最少的飞行次数才能完成清理雪道的任务。
LYD：
类似 <有源汇上下界可行流> 的构图方法，但是不添加T到S的边，求一次超级源到超级汇的最大流。
加边(T,S,0,+∞)，在上一步残量网络基础上再求一次超级源到超级汇的最大流。
流经T到S的边的流量就是最小流的值。
该算法的思想是在第一步中尽可能填充循环流，以减小最小流的代价。
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<queue>#define inf 0x3f3f3f3f#define N 155#define M 400005using namespace std;int head[N],ver[M],nxt[M],f[M],tot,ch[N];void add(int a,int b,int c){ tot++;nxt[tot]=head[a];head[a]=tot;ver[tot]=b;f[tot]=c; tot++;nxt[tot]=head[b];head[b]=tot;ver[tot]=a;f[tot]=0; return ;}queue<int>q;int S,T;bool tell(){ memset(ch,-1,sizeof(ch)); q.push(S);ch[S]=0; while(!q.empty()) { int tmp=q.front();q.pop(); for(int i=head[tmp];i;i=nxt[i]) { if(f[i]&&ch[ver[i]]==-1) { ch[ver[i]]=ch[tmp]+1; q.push(ver[i]); } } } return ch[T]!=-1;}int zeng(int a,int b){ if(a==T)return b; int r=0; for(int i=head[a];i&&b>r;i=nxt[i]) { if(f[i]&&ch[ver[i]]==ch[a]+1) { int t=zeng(ver[i],min(f[i],b-r)); f[i]-=t;f[i^1]+=t;r+=t; } } if(!r)ch[a]=-1; return r;}int dinic(){ int r=0,t; while(tell())while(t=zeng(S,inf))r+=t; return r;}int n;int ru[N],chu[N];int main(){ scanf("%d",&n);tot=1; int SS=n+1,TT=n+2; for(int i=1;i<=n;i++) { int tmp,t; scanf("%d",&tmp); for(int j=1;j<=tmp;j++) { scanf("%d",&t); add(i,t,inf); chu[i]++;ru[t]++; } } for(int i=1;i<=n;i++) { add(SS,i,inf);add(i,TT,inf); } S=n+3,T=n+4; for(int i=1;i<=n;i++) { if(chu[i]>ru[i]) { add(i,T,chu[i]-ru[i]); } else add(S,i,ru[i]-chu[i]); } dinic(); add(TT,SS,inf); dinic(); printf("%d\n",f[tot]); return 0;}
bzoj 2502: 清理雪道 最小流
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。