动态规划:NOI2013 快餐店
2024-10-18 19:25:09
Description
小 T打算在城市C开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的,小T希望快餐店的地址选在离最远的顾客距离最近 的地方。 快餐店的顾客分布在城市C的N 个建筑中,这N 个建筑通过恰好N 条双向道路连接起来,不存在任何两条道路连接了相同的两个建筑。任意两个建筑之间至少存在一条由双向道路连接而成的路径。小T的快餐店可以开设在任一建筑 中,也可以开设在任意一条道路的某个位置上(该位置与道路两端的建筑的距离不一定是整数)。 现给定城市C的地图(道路分布及其长度),请找出最佳的快餐店选址,输出其与最远的顾客之间的距离。
Input
第一行包含一个整数N,表示城市C中的建筑和道路数目。
接下来N行,每行3个整数,Ai,Bi,Li(1≤i≤N;Li>0),表示一条道路连接了建筑Ai与Bi,其长度为Li 。
Output
仅包含一个实数,四舍五入保留恰好一位小数,表示最佳快餐店选址距离最远用户的距离。
注意:你的结果必须恰好有一位小数,小数位数不正确不得分。
Sample Input
1 2 1
1 4 2
1 3 2
2 4 1
1 4 2
1 3 2
2 4 1
Sample Output
2.0
HINT
数据范围
对于 10%的数据,N<=80,Li=1;
对于 30%的数据,N<=600,Li<=100;
对于 60% 的数据,N<=2000,Li<=10^9;
对于 100% 的数据,N<=10^5,Li<=10^9
这个DP有点屌……
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N=;
int n,cnt,fir[N],nxt[N<<],to[N<<];
LL val[N<<],dis[N],ans,sum,Mx;
LL u1[N],v1[N],b[N],c[N];
LL u2[N],v2[N];
bool ring[N];
void addedge(int a,int b,int v){
nxt[++cnt]=fir[a];
val[cnt]=v;
fir[a]=cnt;
to[cnt]=b;
} int ID[N],tot;
int st[N],top;
int pre[N];
void DFS(int x){
ID[x]=++tot;
for(int i=fir[x],y;i;i=nxt[i])
if((y=to[i])!=pre[x]){
if(!ID[y]){
pre[y]=x;
c[y]=val[i];
DFS(y);
}
else if(ID[y]>ID[x]){
while(x!=y){
st[++top]=y;
b[top]=c[y];
ring[y]=true;
y=pre[y];
}
st[++top]=x;
b[top]=val[i];
ring[x]=true;
return;
}
}
} void DP(int x,int fa){
for(int i=fir[x];i;i=nxt[i])
if(to[i]!=fa&&!ring[to[i]]){
DP(to[i],x);
ans=max(ans,dis[x]+dis[to[i]]+val[i]);
dis[x]=max(dis[x],dis[to[i]]+val[i]);
}
} int main(){
freopen("foodshop.in","r",stdin);
freopen("foodshop.out","w",stdout);
scanf("%d",&n);
for(int i=,x,y,v;i<=n;i++){
scanf("%d%d%d",&x,&y,&v);
addedge(x,y,v);addedge(y,x,v);
}
DFS();
for(int i=;i<=top;i++)DP(st[i],); for(int i=;i<=top;i++){
sum+=b[i-];
u1[i]=max(u1[i-],sum+dis[st[i]]);
v1[i]=max(v1[i-],sum+dis[st[i]]+Mx);
Mx=max(Mx,dis[st[i]]-sum);
}
LL tmp=b[top];Mx=sum=b[top]=;
for(int i=top;i>=;i--){
sum+=b[i];
u2[i]=max(u2[i+],sum+dis[st[i]]);
v2[i]=max(v2[i+],sum+dis[st[i]]+Mx);
Mx=max(Mx,dis[st[i]]-sum);
}
LL Mn=v1[top];
for(int i=;i<top;i++)
Mn=min(Mn,max(max(v1[i],v2[i+]),tmp+u1[i]+u2[i+]));
ans=max(ans,Mn);
printf("%.1lf",ans/2.0);
return ;
}
最新文章
- Vue 方法与事件处理器
- golang坑1
- GO语言练习:不定参数函数
- iOS - Swift NSDate		时间
- JXTA中定义自己的成员服务
- 全分布式环境下,DataNode不启动的问题解决
- Qt属性系统
- [Android] App在三星某些机子上闪退:";不保留活动";
- 关于array_agg 函数
- 老李案例分享:定位JAVA内存溢出
- php与MySQL(php内置mysql函数)
- nGrinder 简易使用教程
- asp.net应用发布到IIS无法链接到oracle数据库
- 使用Myeclipse为数据表创建hibernate实体对象
- Jmeter工具进行一个完整的接口测试
- 每天一个linux命令:free
- POJ 1655.Balancing Act 树形dp 树的重心
- [转帖] testin 安全测试要点
- modelsim仿真正确FPGA运行不正确的可能原因 - cm4写寄存器错
- RN 数据持久化存储服务API