NOIP 2009 최 우수 무역 (tarjan + dfs)

제목 설명 Description
[문제 설명] C 국 가 는 n 개의 대도시 와 m 개의 도 로 를 가지 고 모든 도 로 는 이 n 개 도시 중의 한 두 도 시 를 연결한다.임의의 두 도시 사이 에는 최대 한 개의 도로 만 이 직접 연결 되 어 있다.이 m 개 도로 중 일 부 는 단 방향 으로 통행 하 는 도로 이 고 일 부 는 양 방향 으로 통행 하 는 도로 이 며 양 방향 으로 통행 하 는 도 로 는 통계 건수 때 도 1 개 로 집계 된다.C 국 가 는 땅 이 넓 고 각지 의 자원 분포 상황 이 각각 다 르 기 때문에 같은 상품 이 서로 다른 도시 에서 의 가격 이 반드시 같 지 않다.그러나 같은 상품 의 같은 도시 에서 의 매입 가와 판매 가 는 항상 같다.상인 아 룡 이 C 국 을 여행 하 러 왔 다.그 는 같은 상품 이 서로 다른 도시 에서 의 가격 이 다 를 수 있다 는 정 보 를 알 게 된 후에 여행 을 하 는 동시에 상품 이 서로 다른 도시 에서 의 차액 을 이용 하여 여 비 를 조금 벌 기로 결정 했다.C 국 n 개 도시 의 레이 블 을 1 ~ n 으로 설정 하고 아 론 은 1 번 도시 에서 출발 해 n 번 도시 에서 자신의 여행 을 끝내기 로 했다.여행 하 는 과정 에서 모든 도 시 는 여러 번 반복 할 수 있 지만 모든 n 개 도 시 를 거 치 는 것 을 요구 하지 않 는 다.아 론 은 이런 무역 방식 으로 여 비 를 벌 었 다. 그 는 지나 가 는 도 시 를 선택 하여 자신 이 가장 좋아 하 는 상품 인 수정 구 를 구입 하고 그 후에 지나 가 는 다른 도시 에서 이 수정 구 를 팔 아 벌 어 들 인 차액 을 여비 로 삼 았 다.아 론 은 주로 C 개국 을 여행 하기 때문에 그 는 이 무역 을 가장 많이 하기 로 결정 했다. 물론 차액 을 벌 지 못 할 경우 무역 을 할 필요 가 없다.C 국유 5 개 대도 시 를 가정 하면 도시 의 번호 와 도로 연결 상황 은 다음 과 같다. 단 방향 화살 표 는 이 도 로 를 단 방향 통행 이 라 고 표시 하고 양 방향 화살 표 는 이 도 로 를 양 방향 통행 이 라 고 표시 한다.
1 ~ n 번 도시 의 수정 구 가격 이 각각 4, 3, 5, 6, 1 이 라 고 가정 합 니 다.아 룡 은 다음 과 같은 노선 을 선택 할 수 있다. 1 - > 2 - > 3 - > 5. 그리고 2 번 도시 에서 3 번 가격 으로 수정 구 를 구 매 하고 3 번 도시 에서 5 번 가격 으로 수정 구 를 판매 하 며 번 여비 수 는 2 이다.아 룡 도 다음 노선 1 - > 4 - > 5 - > 4 - > 5 를 선택 할 수 있 으 며, 1 번 도시 에 도 착 했 을 때 수정 구 를 1 가격 에, 2 번 도시 에 도 착 했 을 때 수정 구 를 6 가격 에 팔 아 번 여비 수 는 5 다.
현재 n 개 도시 의 수정 구 가격, m 개 도로 의 정보 (각 도로 가 연 결 된 두 도시 의 번호 와 이 도로 의 통행 상황) 를 제공 합 니 다.아 룡 에 게 그 가 최대 얼마의 여 비 를 벌 수 있 는 지 알려 주세요.
입력 설명 Input Description
첫 번 째 줄 은 두 개의 정수 n 과 m 를 포함 하고 중간 에 하나의 빈 칸 으로 나 누 어 도시 의 수량 과 도로 의 수량 을 나타 낸다.두 번 째 줄 n 개의 정수, 두 개의 정수 사이 에 하나의 빈 칸 으로 나 누 어 레이 블 순서에 따라 이 n 개 도시 의 상품 가격 을 표시 합 니 다.다음 m 줄 은 줄 마다 3 개의 정수, x, y, z 가 있 고 두 개의 정수 사 이 를 빈 칸 으로 분리 합 니 다.만약 z = 1 이 라면 이 도 로 는 도시 x 에서 도시 y 사이 의 단 방향 도로 임 을 나타 낸다.만약 z = 2 라면 이 도 로 는 도시 x 와 도시 y 사이 의 양 방향 도로 임 을 나타 낸다.
출력 설명 Output Description
1 개의 정 수 를 포함 하여 가장 많이 벌 수 있 는 여 비 를 나타 낸다.무역 을 하지 않 으 면 0 을 수출 합 니 다.
샘플 입력 Sample Input
5 5 4 3 5 6 1 1 2 1 1 4 1 2 3 2 3 5 1 4 5 2
샘플 출력 Sample Output
5
데이터 범위 및 알림 Data Size & Hint
1 ≤ n ≤ 100000, 1 ≤ m ≤ 500000, 수정 구 가격 ≤ 100.
이 문 제 는 고리 가 있 으 면 마음대로 돌아 다 닐 수 있다 는 성질 을 쉽게 생각 할 수 있다. 즉, 이 고리 의 최고 치 는 모두 마음대로 찾 을 수 있다.이렇게 되면 우 리 는 모든 링 을 점 으로 줄 이 고 원래 링 의 최대 와 최소 치 를 이 링 의 가중치 로 한다. 축 소 된 그림 은 바로 무 환 도 이다. 위 에서 DP 를 한 번 뛸 수 있다. f [u] 는 연결 블록 u 에서 종점 이 있 는 연결 블록 의 모든 경로 에서 가장 큰 점 권 (원래 의 강 한 연결 블록 중의 최대 치) 을 나타 내 고 이전 은 간단 하지만 주의해 야 한다. f [u]의 초기 값 은 모두 0 으로 설정 해 야 합 니 다. dfs 가 종점 에 있 는 연결 블록 이 있 을 때 만 종점 에 있 는 연결 블록 을 자신의 f 값 으로 하고 다른 것 은 출구 가 가리 키 는 연결 블록 이 f 값 (설명 이 종점 에 도착 할 수 있 음) 이 있 을 때 만 이동 할 수 있 습 니 다. 종점 에 도착 하지 못 하 는 무효 점 의 방 해 를 차단 할 수 있 습 니 다.

#include<iostream>
#include<cstdio>
#include<cstring>
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int MAXN = 100010, MAXM = 1000010;
int N, M, ans;

struct Node {
	int to; Node*next;
}Edge[MAXM], *ecnt=Edge, *adj[MAXM];
inline void addedge(int a,int b) {
	++ecnt; ecnt->to = b;
	ecnt->next=adj[a]; adj[a] = ecnt;
}

int belong[MAXN], bcnt;//              
int bmx[MAXN], bmn[MAXN];//                 
int tmr, dfn[MAXN], low[MAXN];
int sta[MAXN], tp;
int val[MAXN];
int x[MAXM], y[MAXM], type[MAXM];
bool insta[MAXN];

void tarjan(int u)
{
	dfn[u] = low[u] = ++tmr;
	sta[++tp] = u;
	insta[u] = 1;
	for (Node*p = adj[u]; p; p = p->next) {
		int &v = p->to;
		if (!dfn[v]) {
			tarjan(v);
			low[u] = Min(low[u], low[v]);
		}
		else if (insta[v])
			low[u] = Min(low[u], dfn[v]);
	}
	if (low[u] == dfn[u]) {
		++bcnt;
		int i;
		do {
			i = sta[tp];
			belong[i] = bcnt;
			bmx[bcnt] = Max(bmx[bcnt], val[i]);
			bmn[bcnt] = Min(bmn[bcnt], val[i]);
			insta[i] = 0; --tp;
		} while (tp>0 && i!=u);
	}
}

int f[MAXN];
bool vis[MAXN];
void dfs(int u) {
	vis[u] = 1;
	if (u==belong[N]) f[u] = Max(f[u], bmx[u]);
	for (Node*p = adj[u]; p; p = p->next) {
		if (!vis[p->to]) dfs(p->to);
		f[u] = Max(f[u], f[p->to]);
	}
	if (f[u]) f[u] = Max(f[u], bmx[u]);//  f[u] 0，           ，     
	ans = Max(ans, f[u] - bmn[u]);//         -         
}

int main()
{
	int i;
	scanf("%d%d", &N, &M);
	for (i = 1; i<=N; ++i) {
		scanf("%d", val+i);
		bmx[i]=-1, bmn[i]=999999;
	}
	for (i = 1; i<=M; ++i) {
		scanf("%d%d%d", &x[i], &y[i], &type[i]);
		addedge(x[i], y[i]);
		if (type[i]==2) addedge(y[i], x[i]);
	}
	tarjan(1);
	memset(adj, 0, sizeof adj);
	ecnt = Edge;
	for (i = 1; i<=M; ++i)
		if (belong[x[i]] != belong[y[i]])
			addedge(belong[x[i]], belong[y[i]]);
	dfs(belong[1]);
	printf("%d
", ans);
	return 0;
}