Codeforces 667D World Tour【最短路+枚举】

垃圾csdn，累感不爱！

题目链接：

http://codeforces.com/contest/667/problem/D

题意：

在有向图中找到四个点，使得这些点之间的最短距离之和最大。

分析：

最简单的Bellman求最短路复杂度太高。可以对每个点进行一次bfs，获得所有连通的点之间的最短距离。

点数最多3000，枚举中间两个点\(i,j\)，对于点\(i\)考虑反向边的最远距离，对于点\(j\)考虑正向边的最远距离。

由于题目说点不同，所以对于每个点我们保存前三个远的点并枚举求得最远距离即可。这样枚举下来时间复杂度\(O(n^2)\)。

代码：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<vector>

#include<queue>

#include<algorithm>

using namespace std;

const int maxn = 3e3 + 5, oo = 0x3f3f3f3f;

int d[maxn][maxn];

int n, m;

typedef pair<int, int>p;

vector<p>zz[maxn], rzz[maxn];

vector<int>G[maxn];

void bfs()

{

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

        queue<int>q;

        q.push(i);

        while(!q.empty()){

            int u = q.front(); q.pop();

            for(int j = 0; j <G[u].size(); j++){

                int w = G[u][j];

                if(d[i][w] != oo) continue;

                d[i][w] = d[i][u] + 1;

                q.push(w);

            }

        }

    }

}

int main (void)

{

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

    memset(d, 0x3f, sizeof(d));

    for(int i = 1; i <= n; i++) d[i][i] = 0;

    int u, v;

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

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

        G[u].push_back(v);

    }

    bfs();

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

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

            if(i == j) continue;

            if(d[i][j] != oo) zz[i].push_back(p(d[i][j], j));

            if(d[j][i] != oo) rzz[i].push_back(p(d[j][i], j));

        }

        sort(zz[i].begin(), zz[i].end());

        sort(rzz[i].begin(), rzz[i].end());

    }

    int r1, r2, r3, r4;

    int maxx = 0;

    int res;

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

        int a = zz[i].size();

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

            int b = rzz[j].size();

            if(i == j || d[j][i] == oo) continue;

            for(int k= a - 1; k >= a - 3 && k >= 0; k--){

                if(zz[i][k].second == j) continue;

                for(int y = b - 1; y >= b - 3 && y >= 0; y--){

                    if(zz[i][k].second == rzz[j][y].second) continue;

                    if(rzz[j][y].second == i)  continue;

                    res = d[j][i] + rzz[j][y].first + zz[i][k].first;

                    if(res > maxx){

                        maxx = res;

                        r1 = rzz[j][y].second, r2 = j, r3 = i, r4 = zz[i][k].second;

                    }

                }

            }

        }

    }

    //cout<<maxx<<endl;

    printf("%d %d %d %d\n", r1, r2, r3, r4);

}

巴特西

Codeforces 667D World Tour【最短路+枚举】

题目链接：

题意：

分析：

代码：

最新文章

热门文章