2013-2014 ACM-ICPC Pacific Northwest Regional Contest B.Bones’s Battery

题意略。

思路：

这个题目求的是第一个可行解，由此想到用二分试探的方式来解决。

现在讲讲怎么验证该解是否合理：

先用floyd求出两两之间的最短距离。

dp[ i ][ j ]表示，i 到 j 至少要充几次电，如果dist[ i ][ j ] <= 当前规定的试探值，那么令dp[ i ][ j ] = 1，否则赋值为INF，表示不知道要充几次电，

这个要靠第二次Floyd来更新。在第二次跑完Floyd之后，看dp数组中的最大值，如果最大值小于k，那么说明合法。

详见代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL F = 0x3f;

LL dist[][];

LL dp[][];

int n,k,m;

void init(){

    memset(dist,F,sizeof(dist));

    memset(dp,F,sizeof(dp));

}

void floyd1(){

    for(int i = ;i < n;++i)

        dist[i][i] = ;

    for(int k = ;k < n;++k)

        for(int i = ;i < n;++i)

            for(int j = ;j < n;++j)

                dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]);

}

void floyd2()

{

    for(int i = ;i < n;++i)

        dp[i][i]=;

    for(int k = ;k < n;++k)

        for(int i = ;i < n;++i)

            for(int j = ;j < n;++j)

                dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j]);

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d%d",&n,&k,&m);

        init();

        int u,v,d;

        for(int i = ;i<m;i++)

        {

            scanf("%d%d%d",&u,&v,&d);

            dist[u][v] = dist[v][u] = d;

        }

        floyd1();

        LL l = ,r = INF;

        LL ans = r;

        LL mid;

        while(l <= r)

        {

            mid = (l + r)>>;

            for(int i = ;i < n;++i)

                for(int j = ;j < n;++j)

                    dp[i][j] = dist[i][j] <= mid ?  : INF;

            floyd2();

            LL d = ;

            for(int i = ;i < n;++i)

                for(int j = ;j < n;++j)

                    if(dp[i][j] > d) d = dp[i][j];

            if(d <= k){

                ans = mid;

                r = mid - ;

            }

            else{

                l = mid + ;

            }

        }

        printf("%lld\n",ans);

    }

    return ;

}

巴特西

2013-2014 ACM-ICPC Pacific Northwest Regional Contest B.Bones’s Battery

最新文章

热门文章