hdu 4126 Genghis Khan the Conqueror

 

       1、将原来最小生成树的边，换成新边的新生成树的长度。

 

       2、把原来的边删除，原图上从新生成最小生成树。

 

第一个问题比较容易解决，直接用原生成树，算就可以。仔细想一下第二个问题，我们可以发现，如果在原来最小生成树的基础上把一条边删除然后替换成其他边的话，相当于求两个最小生成树的次小距离。这样的话，我们只需要像prim求最小生成树的思想一样，利用一颗树中的点，去更新到另一颗树的距离，就可求出最短的距离了（删掉原来的那条边），这样的话时间复杂度是O（n*n），可以接受。dp[ u ][ v ]表示把边u - v 边删去，两颗树的最短距离。

 

 

#include<algorithm>  
#include<iostream>  
#include<cstring>  
#include<cstdio>  
#include<vector>  
#include<cmath>  
#define LL long long  
#define CLR(a, b) memset(a, b, sizeof(a))  
  
using namespace std;  
  
const int N = 3003;  
const int INF = 0x3f3f3f3f;  
  
struct Edge  
{  
    int u, v, c;  
}G[N * N * 2], E[N << 1];  
  
int G_fir[N], G_next[N * N * 2];  
int n, G_tot, d[N], fa[N];  
int fir[N], next[N << 1], tot;  
int mark[N][N];  
int map[N][N];  
bool vis[N];  
int dp[N][N], pri;  
  
void G_Add_Edge(int u, int v, int c)  
{  
    map[u][v] = c;  
    G[G_tot].u = u, G[G_tot].v = v, G[G_tot].c = c;  
    G_next[G_tot] = G_fir[u], G_fir[u] = G_tot ++;  
}  
  
void Add_Edge(int u, int v)  
{  
    E[tot].u = u, E[tot].v = v;  
    next[tot] = fir[u], fir[u] = tot ++;  
}  
  
void prim()  
{  
    int i, num = 1, u = 0, best = INF, v, f, j;  
    CLR(vis, 0);CLR(mark, -1);pri = 0;  
    for(i = 0; i < n; i ++) d[i] = INF;  
    while(num < n)  
    {  
        vis[u] = 1;best = INF;  
        for(i = G_fir[u]; ~i; i = G_next[i])  
        {  
            v = G[i].v;  
            if(!vis[v] && d[v] >= G[i].c)  
            {  
                fa[v] = i;  
                d[v] = G[i].c;  
            }  
        }  
        for(i = 0; i < n; i ++)  
        {  
            if(!vis[i] && d[i] < best)  
            {  
                best = d[i];  
                j = fa[i];  
            }  
        }  
        pri += best;  
        mark[G[j].v][G[j].u] = mark[G[j].u][G[j].v] = best;  
        Add_Edge(G[j].u, G[j].v);  
        Add_Edge(G[j].v, G[j].u);  
        u = G[j].v;  
        num ++;  
    }  
}  
  
int dfs(int pos, int u, int fa)//用点pos去更新任意两颗生成树的距离  
{  
    int i, v, j, ret = INF, cmp;  
    for(i = fir[u]; ~i; i = next[i])  
    {  
        v = E[i].v;  
        if(v != fa)  
        {  
            cmp = dfs(pos, v, u);  
            ret = min(ret, cmp);  
            dp[u][v] = dp[v][u] = min(dp[u][v], cmp);  
        }  
    }  
    if(fa != pos)  
        ret = min(ret, map[pos][u]);  
    return ret;  
}  
  
int main()  
{  
    //freopen("input.txt", "r", stdin);  
    int m, i, j , u, v, c, q;  
    double ans;  
    while(scanf("%d%d", &n, &m), n + m)  
    {  
        G_tot = tot = 0; CLR(fir, -1);  
        CLR(G_fir, -1);CLR(dp, INF);  
        CLR(map, INF);  
        for(i = 0; i < m; i ++)  
        {  
            scanf("%d%d%d", &u, &v, &c);  
            G_Add_Edge(u, v, c);  
            G_Add_Edge(v, u, c);  
        }  
        prim();  
        for(i = 0; i < n; i ++)  
        {  
            dfs(i, i, -1);  
        }  
        scanf("%d", &q);ans = 0;  
        for(i = 0; i < q; i ++)  
        {  
            scanf("%d%d%d", &u, &v, &c);  
            if(mark[u][v] != -1)  
            {  
                ans += min(c, dp[u][v]) + pri - mark[u][v];  
            }  
            else  
            {  
                ans += pri;  
            }  
        }  
        printf("%.4lf\n", ans / q);  
    }  
}  

 

 

补充：软件开发 , C++ ,