Codeforces 667D World Tour 最短路

链接

题意

给你一个有向稀疏图，3000个点，5000条边。问选出4个点A,B,C,D 使得 A-B, B-C, C-D 的最短路之和最大。

思路

枚举中间两个点，端点就是不与这三个点重复的最大的那个点来更新答案。因为是稀疏图，可以做n遍spfa来维护两两之间的最短路。

代码

#include <iostream>

#include <cstdio>

#include <vector>

#include <stack>

#include <queue>

#include <algorithm>

#include <map>

#include <set>

#include <cmath>

#include <cstring>

#include <string>

#define LL long long

#define INF 0x3f3f3f3f

#define eps 1e-8

#define MAXN 3005

#define MAXM 5005

using namespace std;

struct Edge{

	int to, next;

}edges[MAXM];

int head[MAXN];

int tot;

bool vis[MAXN];

int d[MAXN][MAXN];

int res[5];

vector<pair<int, int> > dis1[MAXN], dis2[MAXN];

void add_edge(int x, int y){

	edges[tot].to = y;

	edges[tot].next = head[x];

	head[x] = tot++;

}

void spfa(int s){

	queue<int> Q;

	memset(vis, 0, sizeof(vis));

	Q.push(s);

	d[s][s] = 0;

	while (!Q.empty()){

		int x = Q.front(); Q.pop();

		for (int i = head[x]; i != -1; i = edges[i].next){

			int y = edges[i].to;

			if (d[s][x] + 1 < d[s][y]){

				d[s][y] = d[s][x] + 1;

			}

			if (vis[y]) continue;

			vis[y] = true;

			Q.push(y);

		}

	}

}

int main(){

#ifndef ONLINE_JUDGE

	freopen("in.txt", "r", stdin);

	//freopen("out.txt", "w", stdout);

#endif // ONLINE_JUDGE

	int n, m;

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

	memset(head, -1, sizeof(head));

	tot = 0;

	int x, y;

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

		scanf("%d%d", &x, &y);

		add_edge(x, y);

	}

	memset(d, INF, sizeof(d));

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

		spfa(i);

	}

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

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

			if (d[i][j] != INF){

				dis1[i].push_back(make_pair(d[i][j], j));

				dis2[j].push_back(make_pair(d[i][j], i));

			}

		}

	}

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

		sort(dis1[i].rbegin(), dis1[i].rend());

		sort(dis2[i].rbegin(), dis2[i].rend());

	}

	int ans = 0;

	memset(res, 0, sizeof(res));

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

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

			if (i == j) continue;

			if (d[i][j] == INF) continue;

			for (int k = 0; k < min(3, (int)dis2[i].size()); ++k){

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

				for (int l = 0; l < min(3, (int)dis1[j].size()); ++l){

					if (j != dis1[j][l].second && i != dis1[j][l].second && dis2[i][k].second != dis1[j][l].second){

						int temp = d[i][j] + dis2[i][k].first + dis1[j][l].first;

						if (temp > ans){

							ans = temp;

							res[0] = dis2[i][k].second, res[1] = i, res[2] = j, res[3] = dis1[j][l].second;

						}

					}

				}

			}

		}

	}

	//printf("%d\n", ans);

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

		printf("%d ", res[i]);

	}

	printf("\n");

}

巴特西

Codeforces 667D World Tour 最短路

链接

题意

思路

代码

最新文章

热门文章