BZOJ2502:清理雪道(有上下界最小流)
2024-08-21 14:11:49
Description
滑雪场坐落在FJ省西北部的若干座山上。
从空中鸟瞰,滑雪场可以看作一个有向无环图,每条弧代表一个斜坡(即雪道),弧的方向代表斜坡下降的方向。
你的团队负责每周定时清理雪道。你们拥有一架直升飞机,每次飞行可以从总部带一个人降落到滑雪场的某个地点,然后再飞回总部。从降落的地点出发,这个人可以顺着斜坡向下滑行,并清理他所经过的雪道。
由于每次飞行的耗费是固定的,为了最小化耗费,你想知道如何用最少的飞行次数才能完成清理雪道的任务。
Input
输入文件的第一行包含一个整数n (2 <= n <= 100) – 代表滑雪场的地点的数量。接下来的n行,描述1~n号地点出发的斜坡,第i行的第一个数为mi (0 <= mi < n) ,后面共有mi个整数,由空格隔开,每个整数aij互不相同,代表从地点i下降到地点aij的斜坡。每个地点至少有一个斜坡与之相连。
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
Solution
每条边的流量界限为$[1,INF]$。 拓扑图的起点和$s$连一下,终点和$t$连一下,上下界为$[0,INF]$。
跑一遍最小流就完事了……
Code
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define N (209)
#define INF (0x7f7f7f7f)
using namespace std; struct Edge{int to,next,flow;}edge[N*N];
int n,m,x,vis[N];
int s,t,ss=,tt=,Depth[N],A[N];
int head[N],num_edge;
queue<int>q; inline int read()
{
int x=,w=; char c=getchar();
while (!isdigit(c)) {if (c=='-') w=-; c=getchar();}
while (isdigit(c)) x=x*+c-'', c=getchar();
return x*w;
} void add(int u,int v,int l)
{
edge[++num_edge].to=v;
edge[num_edge].next=head[u];
edge[num_edge].flow=l;
head[u]=num_edge;
} void Add(int u,int v,int l,int r)
{
add(u,v,r-l); add(v,u,);
A[u]-=l; A[v]+=l;
} int DFS(int x,int low,int t)
{
if (x==t || !low) return low;
int f=;
for (int i=head[x]; i; i=edge[i].next)
if (Depth[edge[i].to]==Depth[x]+)
{
int Min=DFS(edge[i].to,min(low,edge[i].flow),t);
edge[i].flow-=Min;
edge[((i-)^)+].flow+=Min;
f+=Min; low-=Min;
if (!low) break;
}
if (!f) Depth[x]=-;
return f;
} bool BFS(int s,int t)
{
memset(Depth,,sizeof(Depth));
Depth[s]=; q.push(s);
while (!q.empty())
{
int x=q.front(); q.pop();
for (int i=head[x]; i; i=edge[i].next)
if (!Depth[edge[i].to] && edge[i].flow)
{
Depth[edge[i].to]=Depth[x]+;
q.push(edge[i].to);
}
}
return Depth[t];
} int Dinic(int s,int t)
{
int ans=;
while (BFS(s,t)) ans+=DFS(s,INF,t);
return ans;
} int main()
{
n=read(); s=; t=n+;
for (int i=; i<=n; ++i)
{
m=read();
if (!m) Add(i,t,,INF);
for (int j=; j<=m; ++j)
vis[x=read()]=, Add(i,x,,INF);
}
for (int i=; i<=n; ++i) if (!vis[i]) Add(s,i,,INF);
int sum=;
for (int i=; i<=n+; ++i)
if (A[i]>) sum+=A[i], add(ss,i,A[i]), add(i,ss,);
else add(i,tt,-A[i]), add(tt,i,);
add(t,s,INF); add(s,t,);
Dinic(ss,tt);
for (int i=head[ss]; i; i=edge[i].next) edge[i].flow=edge[((i-)^)+].flow=;
for (int i=head[tt]; i; i=edge[i].next) edge[i].flow=edge[((i-)^)+].flow=;
int flow0=edge[num_edge].flow;
edge[num_edge-].flow=edge[num_edge].flow=;
printf("%d\n",flow0-Dinic(t,s));
}
最新文章
- svn恢复被删除的分支 svn del 分支
- 記錄一次CRS-0184: Cannot communicate with the CRS daemon的解決
- ural 2068. Game of Nuts
- yum下载rpm
- WebSphere 集群环境下配置 Quartz集群
- innodb_lru_scan_depth
- Linq转成sql后的分页方法
- [置顶] js中如何复制一个对象,如何获取所有属性和属性对应的值
- 微信小程序 网络请求之设置合法域名
- Unity 总裁 John Riccitiello 发话:VR足以匹敌互联网
- 逐步搭建Lamp环境之vim的三种模式以及基本命令
- 【剑指Offer学习】【面试题21:包括min 函数的栈】
- Spring IOC容器对bean的生命周期进行管理的过程
- 支付宝 net
- BZOJ2671 Calc(莫比乌斯反演)
- ansible(一)
- Excel frequency函数
- 使用Dockerfile构建docker lnmp环境
- Linux ./configure --prefix 命令是什么意思?
- python查找文件相同的和包含汉字的
热门文章
- 使用spring security 2.0 和extjs 3.0实现web登录
- 1.C#知识点:值类型和引用类型
- java.lang.NoClassDefFoundError: Failed resolution of: Landroid/support/v4/animation/AnimatorCompatHelper
- Unix环境高级编程:fork, vfork, clone
- 第三十四天- 线程队列、线程池(map/submit/shutdown/回调函数)
- 在Ubuntu 13.10 中安装配置 Hadoop 2.2.0
- js-react组件生命周期
- element-ui Pagination组件源码分析整理笔记(七)
- JavaScript实现IP地址的输入框方式
- Expo大作战(十八)--expo如何发布成独立应用程序,打包成apk或者ipa,发布到对应应用商店