【kruskal+最小偏心距】wiki1700

施工方案第二季

c国边防军在边境某处的阵地是由n个地堡组成的。工兵连受命来到阵地要进行两期施工。

第一期的任务是挖掘暗道让所有地堡互联互通。现已勘测设计了m条互不相交的暗道挖掘方案，如果这m条暗道都实施挖掘，肯定能达到互联互通的目的。事实上，适当选择其中n-1个方案挖掘，就能实现互联互通，即从每个地堡出发都能到达其他任何一个地堡（允许经过别的地堡）。

连长精心谋算，在m个设计规划中选取了挖掘总距离最短且能保证互联互通的若干个暗道规划实施了挖掘，完成了第一期的施工任务后又接受了第二期的施工任务，要求选择一个地堡进行扩建改造，使其能向每个地堡提供弹药。为了让弹药供应更及时、更快捷，从改扩建的地堡到最远地堡的距离（称为最远输送距离）应当尽量小。

你的任务是先求出第一期施工挖掘的总距离，再求改扩建地堡最远输送距离的最小值。

输入描述

其中第一行是n和m，m>=n
下面的m行每行3个数xi、yi、zi,表示xi到yi的距离是zi
zi<1000000且m个距离互不相等

输出描述

共包含两行，每行一个整数，
第一行是第一期的挖掘总距离，第二行是最远输送距离的最小值。

样例输入

4 5
1 2 1
2 3 2
3 4 3
4 1 4
3 1 5

样例输出

6
3

数据范围及提示

【样例说明】
第一期挖掘1到2、2到3和3到4的3条暗道，第二期选择3号地堡进行改扩建，最远输送距离是3
【数据规模】
60%的数据 n<10且m<20
80%的数据 n<1000且m<2000
100%的数据 n<100000且m<200000

先最小生成树，然后在树上求最小偏心距

最小偏心距的求法是先找到一条最长链，然后在链上求最小中位数

最长链的求法是先从任意一个点开始将整棵树遍历一遍求出离起始点的距离，从离起始点最远的点开始进行遍历，找的最远的点，这两个最远点之间的路径就是最长链

表示代码很丑……

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const long N = 100100, M = 200100;
struct ty
{
    long x, y, l;
    bool operator < (const ty &a) const
    {
        if (l < a.l) return true;
			else return false;
    }
}edge[M];
struct ty2
{
    long t, w, next;
}edgenew[M];
long n, m, mm, summ, maxn, dian, re;
long fa[N];
long head[N];
long dist[N];
long pre[N];
bool v[N];
long const INF = 1000000;

void init()
{
    memset(edge, 0 ,sizeof(edge));
    scanf("%d%d", &n, &m);
    for (long i = 0; i < m; i++)
    {
        scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].l);
    }
}
void prepare()
{
    sort (edge, edge + m);
    for (long i = 1; i <= n; i++)
        fa[i] = i;
}
void insertedge(long x, long y, long z, long k)
{
    edgenew[k].t = y;
    edgenew[k].next = head[x];
    edgenew[k].w = z;
    head[x] = k;
}
long findfa(long x)
{
   return fa[x] == x ? x : (fa[x] = findfa(fa[x]));
}
void merge(long x, long y)
{
    fa[findfa(x)] = findfa(y);
}

void kruskal()
{
    long cnt = 0;
    mm = 0;
    long long sum = 0;
    for (long i = 0; i < m; i++)
    {
        long fx = findfa(edge[i].x);
        long fy = findfa(edge[i].y);
        if (fx != fy)
        {
            merge(fx, fy);
            cnt++;
            mm++;
            insertedge(edge[i].x, edge[i].y, edge[i].l, mm);
            mm++;
            insertedge(edge[i].y, edge[i].x, edge[i].l, mm);
            sum += edge[i].l;
            if (cnt >= n - 1) break;
        }
    }
    cout << sum<<endl;
}

void dfs(long x)
{
    long i = head[x];
    for (long i = head[x]; i != 0; i = edgenew[i].next)
        if (!v[edgenew[i].t])
        {
            v[edgenew[i].t] = true;
            pre[edgenew[i].t] = x;
            dist[edgenew[i].t] = dist[x] + edgenew[i].w;
            dfs(edgenew[i].t);
            v[edgenew[i].t] = false;
        }
}
void dfs2(long x)
{
    if (pre[x] != 0) dfs2(pre[x]);
    if ((dist[x] >= maxn / 2.0) && (re > dist[x]))
    {
        re = dist [x];
    }
     if ((maxn - dist[x] >= maxn / 2.0) && (re > maxn - dist[x]))
    {
        re = maxn - dist[x];
    }
}
int main()
{
    freopen("1700.in", "r", stdin);
    freopen("1700.out", "w", stdout);
    init();
    prepare();
    kruskal();
    ///带权中位数
    memset(dist, 0, sizeof(dist));
    memset(v, 0, sizeof(v));
    v[1] = true;
    dfs(1);
    maxn = 0, dian = 0;
    for (long i =1; i<=n ;i++)
    {
        if (dist[i] > maxn)
        {
            maxn = dist[i];
            dian = i;
        }
    }

    memset(dist, 0, sizeof(dist));
    memset(pre, 0, sizeof(pre));
    memset(v, 0, sizeof(v));
    v[dian] = true;
    dfs(dian);

    maxn = 0; dian = 0;
    for (long i = 1; i <= n ;i++)
    {
        //cout << dist[i]<<' ';
        if (dist[i] > maxn)
        {
            maxn = dist[i];
            dian = i;
        }
    }
    re = maxn;
    dfs2(dian);

   // cout << maxn << endl;
    cout << re << endl;
    return 0;
}