程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVALive 6622 Absurdistan Roads

UVALive 6622 Absurdistan Roads

編輯：C++入門知識

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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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;
}