UVALive 6622 Absurdistan Roads - c++编程基础

题意：

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