[TIOJ] 1164. 喵喵的旅程

題目連結:http://tioj.infor.org/problems/1164

---

首先，不難發現本題要先找到鄉鎮最遠距離最小及最大的縣市，不過看起來這題限制滿死的，所以該怎麼做呢?這時就要想到C++內建的一個好用的函數minmax_element，於是就把他給的query塞進去，我們就找到了鄉鎮最遠距離最大及最小的縣市，取得後，就發現我們要找那兩個縣市的直徑(點與點之間最遠的距離)，那該怎麼找直徑呢?，就DFS兩次吧，先隨便從一個點開始DFS，找到最遠的那個點後，再從那個點DFS一遍，求出最大的距離即為該圖的直徑

#include "lib1164.h"
#include <bitset>
#include <utility>
#include <algorithm>
#include <vector>

using namespace std;

struct node{
	int child,length;
};

vector<node> graph[1000001];
bitset<1000001> list(0);

pair<int,int> DFS(int which,int l){
	int maxL=l,w=which,size=graph[which].size();
	list[which]=1;
	for(int i=0;i<size;i++){
		int next = graph[which][i].child;
		if (list[next]) continue;
		pair<int,int> tt = DFS(next,l+graph[which][i].length);
		if(tt.first>maxL){
			maxL=tt.first;
			w=tt.second;
		}
	}
	return make_pair(maxL,w);
}

int main(){
	int N = init();
	vector<int> lol;
	for(int i = 0; i< N;i++){
		lol.push_back(i);
	}
	auto result = minmax_element(lol.begin(),lol.end(),query);
	int min = *result.first;
	int max = *result.second;
	MAP M = getct(min);
	int size=M.k;
	for(int i=0;i<size;i++){
		node t;
		t.child = M.y[i];
		t.length = M.len[i];
		graph[M.x[i]].push_back(t);
		t.child = M.x[i];
		graph[M.y[i]].push_back(t);
	}
	int farMin = DFS(0,0).second;
	list.reset();
	farMin = DFS(farMin,0).first;
	list.reset();
	for(int i=0;i<1000001;i++){
		graph[i].clear();
	}
	M = getct(max);
	size=M.k;
	for(int i=0;i<size;i++){
		node t;
		t.child = M.y[i];
		t.length = M.len[i];
		graph[M.x[i]].push_back(t);
		t.child = M.x[i];
		graph[M.y[i]].push_back(t);
	}
	int farMax = DFS(0,0).second;
	list.reset();
	farMax = DFS(farMax,0).first;
	answer(farMin,farMax);
	return 0;
}