Gym - 100676H

这个题真的好难写 T.T
心理阴影系列之一

求树的直径其实就是求最长路
把这个 边双连通分量缩点 + 树的直径的题弄出来
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

这道题的意思大概就是
如果两个点之间有多条路可以到达，那么他们是强连通的，强连通的点互相到达不需要时间，如果不是强连通的那么

#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) //双连通缩点
{
    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;
    }
}