2013年2月8日 星期五

Codeforces 266D BerDonalds

奇怪的題目名字,應該是學 Mcdonalds 的吧

如果他說只能在點上,就好辦了

直接做一次Floyd,就可以得到答案了

但!問題就在於你可以位於其中的無限多個點的其中一個

前面都很無腦,接下來就需要用到好腦袋惹~
(要了解很簡單,但要想到有點難==)

===================================

其實可以這樣想,先想對於一個邊你要到所有人的最短距離

就是,這邊的兩端為 a, b,min( x + dis[ a ][ i ], c - x + dis[ b ][ i ] )對所有 i 的max要最小

直接做枚舉可能答案的動作,是最簡單也是最方便的(比起二分搜或三分搜)

所以就先朝著枚舉答案的方向思考(也就是哪些中間點要試放看看這樣)

假設所有點的集合是這樣(a, b, c, d, e...),將他分成兩個集合A, B

A代表要讓這個邊的 a 去連會是min, B代表要讓這個邊的 b 去連會是min

也就是我們假定對A集合min(剛剛那團) 會是 a 的比較小,B也是同樣的道理

而若是這麼一回事的話,拿A的最大值,B的最大值,就可以組出想要的 x 了。

枚舉A的最大值,然後求B(補集)的最大值,弄出所有可能的X,再取最小的即可。

//By momo
#include
#include
#include
#define N 210
#define INF 999999999
using namespace std;

double ans = INF;
int n, m, dis[N][N];
int a[N*N], b[N*N], c[N*N];
struct pairr{ int a, b; }d[N];
bool comp(pairr x, pairr y){ return x.a > y.a; }

int main (){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++) dis[i][j] = INF;
        dis[i][i] = 0;
    }
    for(int i = 0; i < m; i++){
        scanf("%d%d%d", &a[i], &b[i], &c[i]);
        a[i]--, b[i]--;
        dis[a[i]][b[i]] = dis[b[i]][a[i]] = c[i];
    }
    for(int k = 0; k < n; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                dis[i][j] = min(dis[i][j],
                            dis[i][k] + dis[k][j]);
    for(int i = 0; i < m; i++){
        int C = c[i];
        for(int j = 0; j < n; j++){
            d[j].a = dis[a[i]][j];
            d[j].b = dis[b[i]][j];
        }
        sort(d, d+n, comp);
        int M = d[0].b; ans = min(ans, 1.0*d[0].a);
        for(int j = 1; j < n; j++){
            double val;
            if(d[j].a > M - C && M + C > d[j].a)
                val = (d[j].a+M+C) / 2.0;
            else val = max(d[j].a, M);
            ans = min(ans, val);
            M = max(M, d[j].b);
        }
    }
    printf("%lf\n", ans);
}

1 則留言: