首页 > 代码库 > UVALive 6622 Absurdistan Roads
UVALive 6622 Absurdistan Roads
题意:
n(2000)个点的图 给出它的最短路矩阵 用n条边构造出满足最短路矩阵的图 保证图连通且解存在
思路:
我们可以先保证图连通 那么需要n-1条边 联想到是不是最小生成树??
可以这样想 假设abc点已经连通 现在考虑再加入到连通块中一个点比如d 如果d-b的距离是d到abc三个点中最短的 那么这条边一定要被选 因为如果不选d-b 假设选了d-a 那么d-a已经长于d-b了 所以d-b的距离将不永远得不到满足
这样我们就可以根据最小生成树选出n-1条边了 还差一条 这时我们想知道最短路矩阵是否已经满足了 如果满足 随便加一条重边就好了 (这里可以利用dfs来算出n-1条边时的最短路矩阵 因为Floyd要n^3)
如果不行 我们加哪条边呢?? 很容易想到用新矩阵和原矩阵比较 差异最小的那条边就是要加的 证明和上面差不多 如果不加最小的 就算加了次小的 那么最小的也得不到满足
代码:
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<map> #include<set> #include<vector> #include<queue> #include<cstdlib> #include<ctime> #include<cmath> using namespace std; #define N 2010 #define inf (1<<30) int n, first = 1; int maz[N][N], dis[N], vis[N], link[N]; int f[N][N]; int head[N], tot; struct edge { int u, v, w, next; } ed[N * 2]; void add(int u, int v, int w) { ed[tot].u = u; ed[tot].v = v; ed[tot].w = w; ed[tot].next = head[u]; head[u] = tot++; } void dfs(int now, int start, int len) { for (int i = head[now]; ~i; i = ed[i].next) { int v = ed[i].v; if (!vis[v]) { vis[v] = 1; f[start][v] = len + ed[i].w; dfs(v, start, f[start][v]); } } } int main() { while (~scanf("%d", &n)) { if (first) first = 0; else puts(""); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) scanf("%d", &maz[i][j]); } for (int i = 1; i <= n; i++) { vis[i] = 0; dis[i] = inf; link[i] = -1; head[i] = -1; } tot = 0; dis[1] = 0; memset(f, 0, sizeof(f)); for (int i = 1; i <= n; i++) { int pos, near = inf; for (int j = 1; j <= n; j++) if (!vis[j] && near > dis[j]) { pos = j; near = dis[j]; } if (link[pos] != -1) { printf("%d %d %d\n", link[pos], pos, maz[pos][link[pos]]); add(pos, link[pos], maz[pos][link[pos]]); add(link[pos], pos, maz[pos][link[pos]]); } vis[pos] = 1; for (int j = 1; j <= n; j++) { if (!vis[j] && dis[j] > maz[pos][j]) { link[j] = pos; dis[j] = maz[pos][j]; } } } int a, b, c = inf; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) vis[j] = 0; vis[i] = 1; dfs(i, i, 0); for (int j = 1; j <= n; j++) { if (maz[i][j] < f[i][j] && c > maz[i][j]) { a = i; b = j; c = maz[i][j]; } } } if (c == inf) a = ed[0].u, b = ed[0].v, c = ed[0].w; printf("%d %d %d\n", a, b, c); } return 0; }
UVALive 6622 Absurdistan Roads
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。