Gym 100917F Find the Length（最短路+生成树）

48 阅读 0 评论 32 点赞

我是靠谱客的博主感性豌豆，最近开发中收集的这篇文章主要介绍Gym 100917F Find the Length（最短路+生成树），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：给出一个无向有权图，求出每个点所在的最小环的权值和。

思路：对于当前的点s，要求经过它的最小环，首先可以求出s到所有点的最短路，然后将最短路上的边构造一棵以s为根的生成树。

反证法可以证明，最小环一定是由这棵树上的两个点加一条不在这棵树上的边组合而成的。

然后就可以O(n^2)枚举了，注意枚举的两个点不能同时在s的同一棵子树中，为了解决这个问题dfs一次标记每个点所属的子树。

还有一个问题，为了避免重复边，s到它的儿子节点不能组成环，枚举的时候处理一下即可。

#include<bits/stdc++.h>
#define eps 1e-6
#define LL long long
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

const int MAXN = 310;
const int INF = 0x3f3f3f3f;
int n, w[MAXN][MAXN];
int d[MAXN], fa[MAXN];
int root[MAXN];
bool vis[MAXN];
vector<int> G[MAXN];
void Dijkstra(int s) {
	memset(vis, 0, sizeof(vis));
	memset(d, INF, sizeof(d));
	for (int i = 1; i <= n; i++)
		G[i].clear();
	d[s] = 0;
	fa[s] = 0;
	for (int i = 1; i <= n; i++) {
		int x, m = INF;
		for (int y = 1; y <= n; y++) 
			if(!vis[y] && d[y] < m) {
				m = d[y];
				x = y;
			}
		if (m == INF)
			break;
		vis[x] = 1;
		G[fa[x]].pb(x);
		for (int y = 1; y <= n; y++)
			if (!vis[y] && w[x][y] != -1 && d[x]+w[x][y] < d[y]) {
				d[y] = d[x] + w[x][y];
				fa[y] = x;
			}
	}
}
void dfs(int cur, int r) {
	root[cur] = r;
	for (int i = 0; i < G[cur].size(); i++)
		dfs(G[cur][i], r);
}
int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d", &n); 
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= n; j++)
			scanf("%d", &w[i][j]);
	for (int i = 1; i <= n; i++) {
		int ans = INF;
		Dijkstra(i);
		for (int j = 0; j < G[i].size(); j++)
			dfs(G[i][j], G[i][j]);
		for (int j = 1; j <= n; j++)
			if (j != i && root[j] != j && w[i][j] != -1) 
				ans = min(ans, d[j]+w[i][j]);
		for (int j = 1; j <= n; j++)
			for (int k = 1; k <= n; k++) {
				if (j == k || root[j] == root[k] || w[j][k] == -1 || k == i || j == i || d[k] == INF || d[j] == INF) 
					continue;
				else 
					ans = min(ans, d[j]+d[k]+w[k][j]);
			}
		if (ans == INF) ans = -1;
		printf("%dn", ans);
	}
    return 0;
}