這個題真的好難寫 T.T
心理陰影系列之一

求樹的直徑其實(shí)就是求最長路
把這個 邊雙連通分量縮點(diǎn) + 樹的直徑的題弄出來
H. Capital City
[ Color: Black ]
Bahosain has become the president of Byteland, he is doing his best to make people's lives easier. Now, he is working on improving road networks between the cities.
If two cities are strongly connected, people can use BFS (Bahosain's Fast Service) to travel between them in no time. Otherwise, they have to follow one of the shortest paths between them, and of course, they will use BFS when they can!
Two cities are connected if there is a path between them, and they are strongly connected if after removing any single road they will remain connected.
President Bahosain wants to minimize the maximum distance people have to travel from any city to reach the capital city, can you help him in choosing the capital city?
Input
The first line of input contains one integer T, the number of test cases (1 ≤ T ≤ 64).
The first line of each test case contains two integers n, m (1 ≤ n ≤ 100,000) (0 ≤ m ≤ 200,000), the number of cities and the number of roads, respectively.
Each of the following m lines contains three space-separated integers a, b, c (1 ≤ a, b ≤ n) (1 ≤ c ≤ 100,000), meaning that there is a road of length c connecting the cities a and b.
Byteland cities are connected since Bahosain became the president.
Test cases are separated with a blank line.
Output
For each test case, print the number of the city and length of the maximum shortest path on a single line. If there is more than one possible city, print the one with the minimum number.
Sample Input 1
7 7
1 2 5
1 7 5
3 2 5
1 3 5
3 4 3
6 4 1
4 5 3

Sample Output
1 6

這道題的意思大概就是
如果兩個點(diǎn)之間有多條路可以到達(dá)，那么他們是強(qiáng)連通的，強(qiáng)連通的點(diǎn)互相到達(dá)不需要時(shí)間，如果不是強(qiáng)連通的那么

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<stack>
#define LL long long
using namespace std;
const int maxn = 100010;
const LL inf = 0xffffffffff;
struct arc
{
    int v,w,next;
    arc(int y = 0,int z = 0,int nxt = -1)
    {
        v = y;
        w = z;
        next = nxt;
    }
    bool operator < (const arc &t) const{
        return w < t.w;
    }
}e[1000010];
int hd[maxn],hd2[maxn],low[maxn],dfn[maxn],belong[maxn],tot;
void add(int *head,int u,int v,int w)
{
    e[tot] = arc(v,w,head[u]);
    head[u] = tot++;
    e[tot] = arc(u,w,head[v]);
    head[v] = tot++;
}

int index,cnt,n,m;
stack<int > S;

void Tarjan(int u, int pre) //雙連通縮點(diǎn)
{
    low[u] = dfn[u] = ++index;
    S.push(u);
    bool flag = false;
    for(int i=hd[u];~i;i = e[i].next)
    {
        if(!flag && e[i].v == pre)
        {
            flag = true;
            continue;
        }

        if(!dfn[e[i].v])
        {
            Tarjan(e[i].v,u);
            low[u] = min(low[u], low[e[i].v]);
        }
        else
            low[u] = min(low[u], dfn[e[i].v]);
    }
    if(low[u] == dfn[u])
    {
        int v;
        cnt++;
        do
        {
            v = S.top();S.pop();
            belong[v] = cnt;
        }while(v != u);
    }
}

LL d[2][maxn];
queue<int > Q;
int bfs(int u,int idx)   //樹的直徑
{
    memset(d[idx],-1,sizeof(d[idx]));
    while(!Q.empty()) Q.pop();
    d[idx][u] = 0;
    Q.push(u);
    while(!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        for(int i = hd2[u];~i;i = e[i].next)
        {
            if(d[idx][e[i].v]==-1)
            {
                d[idx][e[i].v] = d[idx][u] + e[i].w;
                Q.push(e[i].v);
            }
        }
    }
    LL ret = -1;
    int id = 0;
    for(int i=1;i<=cnt;i++)
        if(ret < d[idx][i]) ret = d[idx][id = i];
    return id;
}

void init()
{
    for(int i=0;i<maxn;i++)
    {
        hd[i] = hd2[i] = -1;
        low[i] = dfn[i] = belong[i] = 0;
    }
    index = cnt = tot = 0;
    while(!S.empty()) S.pop();
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        init();
        scanf("%d%d",&n,&m);
        for(int i=0;i<m;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(hd,u,v,w);
        }

        for(int i=1;i<=n;i++)
        {
            if(!dfn[i]) Tarjan(i,-1);
        }
        if(cnt == 1)
        {
            puts("1 0");
            continue;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=hd[i];~j;j = e[j].next)
            {
                if(belong[i] == belong[e[j].v]) continue;
                add(hd2,belong[i],belong[e[j].v],e[j].w);
            }

        }
        bfs(bfs(bfs(1,0),0),1);
        LL ret = inf;
        int id = 0;
        for(int i = 1;i<=n;i++)
        {
            int bg = belong[i];
            LL tmp = max(d[0][bg],d[1][bg]);
            if(tmp < ret)
            {
                ret = tmp;
                id = i;
            }
        }
        cout<<id<<' '<<ret<<endl;
    }
}