NOI 2003 무단결석 한 아이

사이트 주소:http://acm.nankai.edu.cn/p1092.html
1092: 무단결석 한 아이
Time Limit: 1500 ms   
Memory Limit: 32000 kB  
Judge type: Multi-cases
Font Style: Aa Aa Aa
크 리 스 의 집 전화 벨 이 울 렸 다. 크 리 스 선생님 의 초조 한 목소리 가 들 려 왔 다. "여보세요, 크 리 스 의 가장 입 니까? 아이들 이 또 수업 에 오지 않 았 는데 시험 을 보고 싶 지 않 습 니까?" 시험 을 보 겠 다 는 말 을 듣 자 크 리 스 의 부 모 는 애가 타서 가능 한 한 짧 은 시간 안에 크 리 스 를 찾기 로 했다.그들 은 크 리 스 선생님 에 게 "예전 의 경험 에 따 르 면 크 리 스 는 지금 반드시 친구 Shermie 나 Yashiro 의 집에 숨어서 '주먹 왕' 게임 을 할 것 이다. 지금 우 리 는 집에 서 크 리 스 를 찾 아 갈 것 이다. 찾 자마자 바로 전 화 를 할 것 이다." 라 고 말 하고 펑 하고 전 화 를 끊 었 다.
Chris 가 거주 하 는 도 시 는 N 개의 거주 지 와 거주 지 를 연결 하 는 여러 개의 양 방향 거리 로 구성 되 어 있 으 며 거리 x 를 지나 면 Tx 분 이 걸린다.두 거주 지 사이 에 통로 가 하나 밖 에 없다 는 것 을 보증 할 수 있다.Chris 의 집 은 점 C 에 있 고 Shermie 와 Yashiro 는 각각 점 A 와 점 B 에 산다.Chris 의 선생님 과 Chris 의 부 모 는 모두 도시 지 도 를 가지 고 있 지만 Chris 의 부 모 는 A, B, C 의 구체 적 인 위 치 를 알 고 있 고 Chris 의 선생님 은 모른다.
Chris 를 빨리 찾기 위해 Chris 의 부 모 는 다음 과 같은 두 가지 규칙 을 준수 할 것 이다.
l A 가 C 가 B 보다 C 가 가깝다 면 크 리 스 의 부 모 는 먼저 Shermie 의 집에 가서 크 리 스 를 찾 고, 찾 지 못 하면 크 리 스 의 부 모 는 다시 Yashiro 의 집에 간다.반대로 해도 역시 그렇다
l Chris 의 부 모 는 항상 두 개의 유일한 통 로 를 따라 걷는다.
분명히 크 리 스 의 선생님 은 크 리 스 의 부모 가 크 리 스 를 찾 는 과정 에서 상기 두 가지 규칙 을 지 킬 것 이라는 것 을 알 고 있 었 다. 그러나 그 는 A, B, C 의 구체 적 인 위 치 를 모 르 기 때문에 지금 그 는 그 에 게 최 악의 상황 에서 크 리 스 의 부 모 는 얼마나 걸 려 야 크 리 스 를 찾 을 수 있 는 지 알려 주 기 를 바란다.
예 를 들 어 위의 그림 에서 이 도 시 는 4 개의 거주 지 와 3 개의 거리 로 구성 되 어 있 고 모든 거 리 를 지나 면 1 분 의 시간 이 걸린다.만약 에 Chris 가 C 점 에 산다 고 가정 하면 Shermie 는 A 점 에 살 고 Yashiro 는 B 점 에 산다. C 에서 B 의 거 리 는 C 에서 A 까지 의 거리 보다 작 기 때문에 Chiris 의 부 모 는 먼저 Yashiro 의 집에 가서 Chris 를 찾 고 찾 지 못 하면 Shermie 의 집에 가서 찾는다.이렇게 되면 최 악의 경우 크 리 스 의 부 모 는 4 분 이 걸 려 야 크 리 스 를 찾 을 수 있다.
Input
입력 한 첫 줄 은 두 개의 정수 N (3 & lt; N & gt; = 200000) 과 M 으로 각각 거주 지 총수 와 거리 총 수 를 나타 낸다.아래 M 줄 은 줄 마다 거리의 정 보 를 드 립 니 다.i + 1 줄 은 정수 Ui, Vi, Ti (1 & lt; = Ui, Vi & gt; = N, 1 & lt; = Ti & gt; = 100000000) 를 포함 하고 거리 i 가 거주 지 Ui 와 Vi 를 연결 하고 거리 i 를 지나 면 Ti 분 이 걸린다 고 표시 한다.거리 정 보 는 중복 되 지 않 는 다.
Output
출력 은 정수 T, 즉 최 악의 경우 Chris 의 부 모 는 T 분 이 걸 려 야 Chris 를 찾 을 수 있 습 니 다.
Sample Input

4 31 2 12 3 13 4 1

Sample Output

4

Hint
데이터 규모 가 어느 정도 줄 어 들 었 으 니 scanf 로 데 이 터 를 읽 는 것 을 권장 합 니 다.
Source
NOI 2003
2007 년 국가 합숙 훈련 팀 진 유 희 의 논문 을 소개 한다.
분석 하 다.
문제 추상
이 문제 의 주 제 는 명확 하 다. 즉, 한 그루 의 나무 에서 각 변 에 하나의 길이 값 이 있다. 현 재 는 나무 에서 3 개의 점 X, Y, Z 를 선택 하여 X 에서 Y 까지 의 거리 가 X 에서 Z 까지 의 거리 보다 크 지 않 고 X 에서 Y 까지 의 거리 와 Y 에서 Z 까지 의 거리 와 최대 치 를 만족 시 켜 이 최대 치 를 구한다.
대충 분석 하 다
분명히 이 문제 의 구조 모델 은 나무 이 고 데이터 의 양 이 많아 서 이 문제 의 방법 을 나무 구조 에 동적 계획 을 사용 하 는 데 접근 하기 쉽다.임의의 노드 a 를 고려 할 때 이 점 을 문제 에서 요구 하 는 노드 Y 로 하면 이 점 에서 가장 먼 두 노드 만 구하 면 된다 는 것 을 쉽게 발견 할 수 있다.그러나 나무 구조 에 있어 서 특정한 노드 에서 가장 먼 두 노드 에 필요 한 복잡 도 를 계산 해 야 한다. 그러나 우 리 는 어느 점 이 답 중의 노드 Y 인지 모 르 기 때문에 반드시 이 점 을 매 거 해 야 한다. 그러면 시간 복잡 도 는 N = 20000 시 에 심각하게 시간 을 초과 할 수 있 기 때문에 이 방법 은 불가능 하 다.
Y 점 을 매 거 하면 시간 이 초과 되 고 매 거 진 사상 을 더 할 수 없 지 않 을 까?생각 을 좀 더 해 볼 수 있다.
매 거 분기 점
특정한 점 a 를 분기점 으로 할 때 이 를 뿌리 로 나 무 를 구성 하고 노드 Y 에 대해 두 가지 상황 이 있다. 첫째, Y 는 노드 a 이다.2Y 는 a 의 한 아이 노드 의 나무 위 에 있다.상황 1 에 대해 상황 2 로 바 꿀 수 있 습 니 다. a 에 빈 아이 노드 를 추가 하고 a 와 의 거리 가 0 이 라 고 생각 하면 됩 니 다.a 가 분기점 인 이상 X 와 Z 는 같은 나무 에 있 을 수 없고 X 와 Y, Y 와 Z 도 같은 나무 에 있 을 수 없다.제목 에서 요구 하 는 것 은 | XY | + | YZ | 최대, 즉 2 | Ya | + | Za | + | Xa | 최대 입 니 다.이로써 사고방식 은 완전히 명확 해 졌 다. a 를 지점 으로 하 는 상황 에 대해 a 의 가장 먼 3 개의 점 만 필요 하고 이 3 개의 점 은 각각 a 의 3 개의 서로 다른 자나무 안에 있다.분기 점 을 매 거 하 는 방법 을 사용한다 면 매번 필요 한 계산 을 해 야 하고 시간 복잡 도 는 또 된다.
두 번 편력 하 다
여기, 생각 을 좀 바 꿔 야 겠 어 요.점 1 을 뿌리 로 하여 요구 하 는 값 을 계산 한 후에 다른 노드 를 매 거 하지 않 고 이 나 무 를 다시 한 번 옮 겨 다 니 며 BFS 를 한 번 진행 합 니 다. 깊이 가 작은 먼저 방문 하고 깊이 가 큰 후에 방문 하면 특정한 노드 에 방문 할 때 아버지 노드 가 이미 방문 되 었 습 니 다.만약 에 우리 가 지금 점 a 를 방문 했다 고 가정 하면 우리 가 지금 요구 하 는 것 은 점 a 의 세 개의 가장 먼 점 이 고 이 세 개의 점 에서 a 까지 의 경 로 는 a 를 제외 한 똑 같은 노드 를 거치 지 않 는 다.분명히 이 세 가지 점 은 a 를 뿌리 로 하 는 나무 에 있 거나 a 를 뿌리 로 하 는 나무 밖 에 있다.만약 에 a 를 뿌리 로 하 는 나무 밖 에 있다 면 반드시 a 의 아버지 노드 를 통 해 a 와 연결 해 야 한다.이에 따라 생각 이 점점 뚜렷 해 졌 다.이번 에는 점 a 에 대해 아버지 노드 를 검사 할 때 아버지 노드 의 가장 먼 곳 에 있 고 a 를 뿌리 로 하 는 서브 트 리 에 있 는 점 이 없 으 면 됩 니 다. 다시 처음으로 구 한 값 과 비교 하면 이 점 을 분기점 으로 할 때 | XY | + | YZ | 의 가장 큰 값 을 구 할 수 있 습 니 다.구체 적 인 방법 은 각 점 에서 가장 큰 두 개의 값 을 기록 하고 이 가장 큰 두 개의 값 이 각각 어느 인접 노드 에서 전 달 된 것 인지 기록 하 는 것 이다.한 아이의 노드 를 옮 겨 다 닐 때 최대 값 이 이 아이의 노드 에서 전달 되 는 지 확인 하고, 만약 그렇다면 큰 값 을 취하 고, 그렇지 않 으 면 최대 값 을 취 할 수 있다.이렇게 되면 이 알고리즘 은 시간 복잡 도와 공간 복잡 도 를 모두 가지 고 매우 우수한 알고리즘 이다.
주의 하 다.
계산 과정 에서 의 값 과 마지막 결 과 는 긴 정형 의 범 위 를 초과 할 수 있 으 므 로 int 64 또는 double 형식 을 사용 해 야 합 니 다.
코드 는 자기가 쓴 거 야.
기본 적 인 사고방식 은 바로 진 유 희 의 사고방식 이다.

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>

using namespace std;

const int maxn=210000;

struct Node{
	int flag;
	long long t;
};

long long Max;
Node cnt[maxn][4];
bool vis[maxn];
vector<Node> son[maxn];

bool cmp(Node a,Node b)
{
	return a.t>b.t;
}

void DFS1(int x)
{
	int i,v;
	for(i=0;i<3;i++)
		cnt[x][i].t=0;
	for(i=0;i<son[x].size();i++)
	{
		v=son[x][i].flag;
		if(!vis[v])
		{
			vis[v]=1;
			DFS1(v);
			cnt[x][3].t=cnt[v][0].t+son[x][i].t;
			cnt[x][3].flag=v;
			sort(cnt[x],cnt[x]+4,cmp);
		}
	}
	if(cnt[x][0].t+2*cnt[x][1].t+cnt[x][2].t>Max)
		Max=cnt[x][0].t+2*cnt[x][1].t+cnt[x][2].t;
}

void DFS2(int x,long long ff)
{
	int i,v;
	for(i=0;i<son[x].size();i++)      //         。
	{
		v=son[x][i].flag;
		if(vis[v])
		{
			if(cnt[v][0].flag!=x)
				cnt[x][3].t=cnt[v][0].t;
			else
				cnt[x][3].t=cnt[v][1].t;
			cnt[x][3].flag=v;
			cnt[x][3].t+=ff;
			sort(cnt[x],cnt[x]+4,cmp);
			if(cnt[x][0].t+2*cnt[x][1].t+cnt[x][2].t>Max)
				Max=cnt[x][0].t+2*cnt[x][1].t+cnt[x][2].t;
		}
	}
	for(i=0;i<son[x].size();i++)
	{
		v=son[x][i].flag;
		if(!vis[v])
		{
			vis[v]=1;
			DFS2(v,son[x][i].t);
		}
	}
}

int main()
{
	int N,M;
	int i,u,v;
	long long t;
	Node tmp;

	while(scanf("%d%d",&N,&M)==2)
	{
		for(i=1;i<=N;i++)
			son[i].clear();

		for(i=1;i<=M;i++)
		{
			scanf("%d%d%lld",&u,&v,&t);
			tmp.flag=v;	tmp.t=t;	son[u].push_back(tmp);
			tmp.flag=u;	son[v].push_back(tmp);
		}
		Max=0;
		memset(vis,0,sizeof(vis));
		vis[1]=1;
		DFS1(1);
		memset(vis,0,sizeof(vis));
		vis[1]=1;
		DFS2(1,0);
		printf("%lld
",Max);
	}

	return 0;
}