http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1757

二分答案mid

避难所拆为mid个点

每个避难所的第一个点向第二个点,第二个点向第三个点……连inf边

每个点向汇点连流量为1的边

枚举能在mid时间内到达避难所i的点j,假设时间为t,由点j向点i的第t个点连流量为1的边

源点向每个非避难所节点连流量为1的边

最大流判断能否==n-m

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 2001
using namespace std;
int n,m,p,src,decc,cnt;
int front[N*],nxt[N*],to[N*],cap[N*],tot;
int dis[][N];
int cur[N*],lev[N*];
bool vis[N*],safe[N];
const int inf=2e9;
void add(int u,int v,int w)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; cap[tot]=w;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; cap[tot]=;
}
void build(int mid)
{
memset(front,,sizeof(front));
tot=; decc=n+m*mid+;
for(int i=;i<=m;i++)
{
for(int j=;j<mid;j++)
add(n+mid*(i-)+j,n+mid*(i-)+j+,inf);
for(int j=;j<=n;j++)
if(!safe[j] && dis[i][j]<=mid)
add(j,n+mid*(i-)+dis[i][j],);
}
for(int i=n+;i<decc;i++) add(i,decc,inf);
for(int i=;i<=n;i++) if(!safe[i]) add(src,i,);
}
bool bfs()
{
for(int i=;i<=decc;i++) cur[i]=front[i],lev[i]=-;
queue<int>q;
vis[src]=true;
lev[src]=;
q.push(src);
int now;
while(!q.empty())
{
now=q.front();
q.pop(); vis[now]=false;
for(int i=front[now];i;i=nxt[i])
if(lev[to[i]]==- && cap[i]>)
{
lev[to[i]]=lev[now]+;
if(to[i]==decc) return true;
if(!vis[to[i]])
{
vis[to[i]]=true;
q.push(to[i]);
}
}
}
return false;
}
int dinic(int now,int flow)
{
if(now==decc) return flow;
int rest=,delta;
for(int & i=cur[now];i;i=nxt[i])
if(lev[to[i]]>lev[now] && cap[i]>)
{
delta=dinic(to[i],min(cap[i],flow-rest));
if(delta)
{
cap[i]-=delta,cap[i^]+=delta;
rest+=delta;
if(rest==flow) break;
}
}
if(rest!=flow) lev[now]=-;
return rest;
}
bool check(int mid)
{
build(mid);
int now=;
while(bfs()) now+=dinic(src,inf);
if(now==n-m) return true;
return false;
}
void dfs(int x,int f,int s)
{
for(int i=front[x];i;i=nxt[i])
if(to[i]!=f)
{
dis[s][to[i]]=dis[s][x]+;
dfs(to[i],x,s);
}
}
int main()
{
scanf("%d%d",&n,&m);
int u,v;
for(int i=;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v,);
}
for(int i=;i<=m;i++)
{
scanf("%d",&u);
safe[u]=true;
dfs(u,,i);
}
int l=,r=n+,mid,ans;
while(l<=r)
{
mid=l+r>>;
if(check(mid)) ans=mid,r=mid-;
else l=mid+;
}
printf("%d",ans);
}
基准时间限制:3 秒 空间限制:262144 KB 分值: 160 难度:6级算法题
 收藏
 关注
死亡之翼降临了!艾泽拉斯大陆的子民们必须逃出他的魔爪!

艾泽拉斯的结构是一棵树,这棵树上的一些节点是地精建造的通往地下避难所的洞口。
除了这些洞口之外,树上的每个节点上都有一个种族,每个种族通过树上的一条边都需要一个单位时间。
因为地精比较矮小,所以洞口很窄,每个单位时间只能让一个种族通过,但是一个单位时间内的一个节点上可以存在多个种族。
地精们需要你求出最少需要多少单位时间才能让所有种族躲进地下避难所。
【注意题目有修改,洞口不一定是叶子节点】
Input
第1行两个整数n(n<=2000)和m(m<=40)表示节点个数和洞口个数
接下来n-1行每行两个整数表示树上的每一条边
第n+1行m个整数表示所有洞口的编号,保证洞口是叶子节点
Output
一个整数t表示让所有种族躲进地下避难所的最少时间
Input示例
6 2
1 2
1 3
1 4
1 5
5 6
3 6
Output示例
3

最新文章

  1. JavaScript多文件下载
  2. Routing 功能概述 - 每天5分钟玩转 OpenStack(98)
  3. 使用ycsb测试cassandra
  4. JPEG文件格式介绍
  5. 【leetcode】Multiply Strings
  6. db2 怎么计算两个时间相差多少个月。如2015-10-10 和2014-1-12
  7. Python拷贝(深拷贝deepcopy与浅拷贝copy)
  8. android开发系列之友盟统计集成
  9. tomcat memory leak
  10. HashMap HashTable HashSet
  11. meta的属性详解
  12. POJ3678【错误总会让自己有收获的】
  13. CentOS 7 安装MySql Server 5.6
  14. 实现类似MVC ViewBag类型的对象
  15. Mac系统安装nginx+rtmp模块
  16. [Note] Yet Another Resource Negotiator
  17. [LeetCode] Bricks Falling When Hit 碰撞时砖头掉落
  18. ftp 发布配置
  19. 20175223 《Java程序设计》 第八周学习总结
  20. NOIP训练测试2(2017081502)

热门文章

  1. 02慕课网《进击Node.js基础(一)》——CommonJs标准
  2. 下载与安装APache Cordova
  3. 漫漫征途,java开发(未完待续)
  4. Access连接数据源配置(新手必知)
  5. mvc4 找到多个与名为“xx”的控制器匹配的类型
  6. c#程序的阅读
  7. 从入门到不放弃——OO第一次作业总结
  8. git找回当前目录下误删的所有文件
  9. C#获取当前路径的方法如下
  10. javascript 常用知识点