[TIOJ] 1164. 喵喵的旅程
題目連結:http://tioj.infor.org/problems/1164
首先,不難發現本題要先找到鄉鎮最遠距離最小及最大的縣市,不過看起來這題限制滿死的,所以該怎麼做呢?這時就要想到C++內建的一個好用的函數minmax_element,於是就把他給的query塞進去,我們就找到了鄉鎮最遠距離最大及最小的縣市,取得後,就發現我們要找那兩個縣市的直徑(點與點之間最遠的距離),那該怎麼找直徑呢?,就DFS兩次吧,先隨便從一個點開始DFS,找到最遠的那個點後,再從那個點DFS一遍,求出最大的距離即為該圖的直徑
首先,不難發現本題要先找到鄉鎮最遠距離最小及最大的縣市,不過看起來這題限制滿死的,所以該怎麼做呢?這時就要想到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;
}
留言
張貼留言