首页 > ACM题库 > HDU-杭电 > HDU 3143-Speedy Escape-分治-[解题报告]HOJ
2014
03-03

HDU 3143-Speedy Escape-分治-[解题报告]HOJ

Speedy Escape

问题描述 :


Rain Fall

The Newton brothers are planning to rob a bank in the city of Alviso and want to figure out a way to escape the city’s only police car. They know that their car is faster than the police car so if they could just reach one of the highways exiting the city they will be able to speed away from the police.

The police car has a maximum speed of 160 km/h. Luckily, the brothers know where the police car will start (it’s parked at the police station). To be on the safe side they assume that the police car will start moving as soon as they leave the bank and start their car (this is when the alarm goes off).

The brothers want to find a fixed route that ensures that they are able to leave the city no matter what route the police car take and at what speed it drives. However, since the brothers are not very confident drivers they don’t want to drive faster than necessary. Luckily they have recently invested in a new hi-tech in-car police escape system that you have constructed. This system will tell them what the minimal top speed needed to escape is (and probably other useful things like what route to take).

Let’s turn the clock back a bit to the time when you were constructing the escape system and focused on finding the minimal required speed. Can you get it right?

You may treat all roads as infinitesimally narrow and both cars as point objects. If the brothers ever end up at the same point (on any road or intersection) at the same time as the police car they will be caught and by Murphy’s law if there is any possibility of this happening it will happen. The two cars start simultaneously and can accelerate/decelerate instantaneously at any time to any speed below or equal to its maximum speed. They can also change roads at intersections or direction anywhere on a road instantaneously no matter what speed they are traveling at.

输入:

The first line of the input consists of three integers n, m and e, where 2 <= n <= 100 describe the number of intersections, 1 <= m <= 5000 describes the number of roads in the city and 1 <= e <= n describes the number of highway exits. Then follow m lines, each consisting of three integers a, b, l such that 1 <= a < b <= n and 1 <= l <= 100 describing a road of length l hundred meters from intersection a to intersection b. Then follows a line of e integers, each one a number in 1, …, n describing which intersections are connected to highway exits. Finally there is a line with two integers b and p (1 <= b, p <= n and b != p) describing the intersections where the brothers and the police cars start, respectively.

It will always be possible to travel from any intersection to any other intersection. Roads are only connected at intersection points (although they may cross using bridges or tunnels at others points). Roads can be used in both directions but there cannot be more than one road between two intersections.

输出:

The first line of the input consists of three integers n, m and e, where 2 <= n <= 100 describe the number of intersections, 1 <= m <= 5000 describes the number of roads in the city and 1 <= e <= n describes the number of highway exits. Then follow m lines, each consisting of three integers a, b, l such that 1 <= a < b <= n and 1 <= l <= 100 describing a road of length l hundred meters from intersection a to intersection b. Then follows a line of e integers, each one a number in 1, …, n describing which intersections are connected to highway exits. Finally there is a line with two integers b and p (1 <= b, p <= n and b != p) describing the intersections where the brothers and the police cars start, respectively.

It will always be possible to travel from any intersection to any other intersection. Roads are only connected at intersection points (although they may cross using bridges or tunnels at others points). Roads can be used in both directions but there cannot be more than one road between two intersections.

样例输入:

3 2 1
1 2 7
2 3 8
1
3 2
3 2 1
1 2 7
2 3 8
1
2 3
4 4 2
1 4 1
1 3 4
3 4 10
2 3 30
1 2
3 4

样例输出:

IMPOSSIBLE
74.6666666667
137.142857143

转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents   
by—cxlove 

题意:给出一个图,其中有一些点是出口,现在有一个罪犯有一个警察,各在两个不同的点。其中警察有一个最大速度160,问罪犯最少需要多大的速度,保证能从某个出口逃跑。

http://acm.hdu.edu.cn/showproblem.php?pid=3143 

yobobobo给推荐的题,当时和他分析了下,点的个数不多,只有100。

对于答案肯定二分,然后我的想法是,首先预处理出每两个点的最短路径,然后判断可行不可行,结果SB了,最短路径肯定不是一条。

但是再一想,n=100,二分之后还是可以暴力搞的。

由于 各种问题,中途也出现了各种奇葩错误。

我开始求的最短路求的是时间,然后对于每个二分的速度,我都要求一次spfa,果断超时。

然后就假设一个速度,求一次spfa,之后根据比例转换一下。还是各种不能过

其间和yobobobo两份错误代码,对拍,还是发现了错误,然后yobobobo过了,我还在跪。

发现我写的spfa不太好,影响精度,直接spfa两次,从罪犯和警察的起点出现,求出到各个点的最短路径长度。这样就是整数,而且在之后的判断中,可以把除法优化成乘法,确保了精度问题。

当中有一步,是可以通过所有点预处理一下,罪犯的速度上界,yobobobo的做法是首先跑一遍bfs或者spfa判断是否可行。也就 是罪犯一定能逃脱的前提是存在一条路径,不经过警察的起点,能到达终点,因为罪犯的速度可以为正无穷。

但是我还是各种WA,找了yobobobo对拍了数据,各种姿势调整后,终于过了,而且还测了各种其它姿势。

注意的地方:

1、对于无解可以spfa或者bfs判断一下,上面提出的有解的必要条件肯定没问题

2、对于罪犯对整个图的最短路,需要注意的是不能经过警察的起点

3、在二分速度之后,判断可以bfs,或者dfs,便是判断可以走到哪些点,条件就是罪犯到达的时间早于警察到达的时间,如果可以则扩展,注意的是每个点只需要判断一次,不需要像DFS那样恢复现场

4、这题的精度要求是1e-6,可是sample给的精度很高,误导了yobobobo,搞得我们都用了1e-10,其实姿势正确1e-6就能过,原以为样例小数据都能这么大误差,所以把精度控制地很严,导致多次TLE

PS:spfa写错好几个地方 ,SB到极点

#include<iostream>  
#include<cstdio>  
#include<map>  
#include<cstring>  
#include<cmath>  
#include<vector>  
#include<algorithm>  
#include<set>  
#include<string>  
#include<queue>  
#define inf 1600005  
#define M 40  
#define N 200005  
#define maxn 300005  
#define eps 1e-7
#define zero(a) fabs(a)<eps  
#define Min(a,b) ((a)<(b)?(a):(b))  
#define Max(a,b) ((a)>(b)?(a):(b))  
#define pb(a) push_back(a)  
#define mp(a,b) make_pair(a,b)  
#define mem(a,b) memset(a,b,sizeof(a))  
#define LL unsigned long long  
#define MOD 2012  
#define lson step<<1
#define rson step<<1|1
#define sqr(a) ((a)*(a))  
#define Key_value ch[ch[root][1]][0]  
#define test puts("OK");  
#define pi acos(-1.0)
#pragma comment(linker, "/STACK:1024000000,1024000000")  
using namespace std;  
struct Edge{
    int v,w,next;
}e[100005];
int start[105],tot;
bool ext[105];
int p1,p2;
int n,m,ee;
int a[105][105];
int police[105],pep[105];
void add(int u,int v,int w){
    e[tot].v=v;e[tot].w=w;e[tot].next=start[u];
    start[u]=tot++;
}
bool mark;
bool vis[105];
double v_p,v_o=160;
void dfs(int u,int pre){
    if(mark) return;
    if(police[u]*v_p<=pep[u]*v_o) return ;
    vis[u]=true;
    if(ext[u]) {mark=true;return;}
    for(int i=start[u];i!=-1;i=e[i].next){
        int v=e[i].v;
        if(v==pre||vis[v]) continue;
        dfs(v,u);
        if(mark) return ;
    }
}
bool check(double vv){
    mark=false;
    v_p=vv;
    mem(vis,false);
    dfs(p1,0);
    return mark;
}
void slove(){
    double low=0,mid,high=0;
    for(int i=1;i<=n;i++){
        if(!police[i]) continue;
        high=max(high,(double)pep[i]*v_o/police[i]);
    }
    high+=2*eps;
    double ans=-1;
    while(low+eps<high){
        mid=(low+high)/2;
        if(check(mid)){
            ans=mid;
            high=mid;
        }
        else low=mid;
    }
    if(ans<0) puts("IMPOSSIBLE");
    else printf("%.10f\n",ans);
}
void Spfa(int s,int *dist){
    queue<int>que;
    while(!que.empty()) que.pop();
    bool flag[105];mem(flag,false);
    for(int i=1;i<=n;i++) dist[i]=inf;
    dist[s]=0;flag[s]=true;
    que.push(s);
    while(!que.empty()){
        int u=que.front();
        flag[u]=false;
        que.pop();
        for(int i=start[u];i!=-1;i=e[i].next){
            int v=e[i].v,w=e[i].w;
            if(v==p2) continue;
            int tmp=dist[u]+w;
            if(tmp<dist[v]){
                dist[v]=tmp;
                if(!flag[v]){
                    que.push(v);
                    flag[v]=true;
                }
            }
            
        }
    }
}
int main(){
    //freopen("in.in","r",stdin);
    //freopen("out.out","w",stdout);
    while(scanf("%d%d%d",&n,&m,&ee)!=EOF){
        for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=inf;
        tot=0;mem(start,-1);
        while(m--){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);add(v,u,w);
        }  
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(a[i][j]<inf)
                    add(i,j,a[i][j]);
        mem(ext,false);
        for(int i=0;i<ee;i++){
            int k;
            scanf("%d",&k);
            ext[k]=true;
        }
        scanf("%d%d",&p1,&p2);
        Spfa(p1,pep);
        Spfa(p2,police);
        slove();
    }
    return 0;
}





参考:http://blog.csdn.net/acm_cxlove/article/details/8247260


  1. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

  2. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?