【POJ - 3160】Father Christmas flymouse（Tarjan缩点，DAG最长路）

题干：

After retirement as contestant from WHU ACM Team, flymouse volunteered to do the odds and ends such as cleaning out the computer lab for training as extension of his contribution to the team. When Christmas came, flymouse played Father Christmas to give gifts to the team members. The team members lived in distinct rooms in different buildings on the campus. To save vigor, flymouse decided to choose only one of those rooms as the place to start his journey and follow directed paths to visit one room after another and give out gifts en passant until he could reach no more unvisited rooms.

During the days on the team, flymouse left different impressions on his teammates at the time. Some of them, like LiZhiXu, with whom flymouse shared a lot of candies, would surely sing flymouse’s deeds of generosity, while the others, like snoopy, would never let flymouse off for his idleness. flymouse was able to use some kind of comfort index to quantitize whether better or worse he would feel after hearing the words from the gift recipients (positive for better and negative for worse). When arriving at a room, he chould choose to enter and give out a gift and hear the words from the recipient, or bypass the room in silence. He could arrive at a room more than once but never enter it a second time. He wanted to maximize the the sum of comfort indices accumulated along his journey.

Input

The input contains several test cases. Each test cases start with two integers N and M not exceeding 30 000 and 150 000 respectively on the first line, meaning that there were N team members living in N distinct rooms and M direct paths. On the next N lines there are N integers, one on each line, the i-th of which gives the comfort index of the words of the team member in the i-th room. Then follow M lines, each containing two integers i and j indicating a directed path from the i-th room to the j-th one. Process to end of file.

Output

For each test case, output one line with only the maximized sum of accumulated comfort indices.

Sample Input

Sample Output

Hint

32-bit signed integer type is capable of doing all arithmetic.

题目大意：

Flymouse从武汉大学ACM集训队退役后，做起了志愿者，在圣诞节来临时，Flymouse要打扮成圣诞老人给集训队员发放礼物。集训队员住在校园宿舍的不同寝室，为了节省体力，Flymouse决定从某一个寝室出发，沿着有向路一个接一个的访问寝室并顺便发放礼物，直至能到达的所有寝室走遍为止。对于每一个寝室他可以经过无数次但是只能进入一次，进入房间会得到一个数值（数值可正可负），他想知道他能获得最大的数值和。

解题报告：

因为每一个scc中可以无限次走过，但是不一定进入房间（也就是获得对应点的权值），所以我们只需要记录每一个scc中有正贡献的点。然后对缩点完的新图的每个起点进行DP求最长路就可以了。

注意代码姿势非常重要，比如你如果最后建新图的边是遍历每一条边，就必须要新开一个TOT，否则会无限循环。当然，如果你不是遍历到tot，而是遍历到m，那就不存在这个问题了。还有就是set去重时的姿势，别写错了。还有初始化，别落下tot和TOT。。其他的就没啥了，挺简单的一道题。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 3e5 + 5;
int n,m;
set<int> ss[MAX];
struct Edge {
	int to,fr;
	int ne;
} e[MAX*10],E[MAX*10];
int head[MAX],DFN[MAX],LOW[MAX],stk[MAX],vis[MAX],col[MAX],clk,index,scc;
int HEAD[MAX];
int val[MAX],VAL[MAX],IN[MAX],tot,TOT,TMP[MAX];
int DIS[MAX],VIS[MAX];
void add(int u,int v) {//放弃传head数组进来了，因为还得重新弄个tot。  所以还不如直接写两个函数 。以后公用函数时多看看是否有重名的全局变量！！这一般都是坑 
	e[++tot].fr = u;
	e[tot].to = v;
	e[tot].ne = head[u];
	head[u] = tot;
}
void ADD(int u,int v) {//放弃传head数组进来了，因为还得重新弄个tot。  所以还不如直接写两个函数 。以后公用函数时多看看是否有重名的全局变量！！这一般都是坑 
	E[++TOT].fr = u;
	E[TOT].to = v;
	E[TOT].ne = HEAD[u];
	HEAD[u] = TOT;
}
void init() {
	for(int i = 1; i<=n; i++) {
		head[i] = HEAD[i] = -1;//其实不用HEAD的初始化 下面有了 
		DFN[i] = LOW[i] = col[i] = vis[i] = 0;
		DIS[i] = VAL[i] = VIS[i] = IN[i] = TMP[i] = 0;
	}
	clk=index=scc=0;
	tot=TOT=0;
}
void Tarjan(int x) {
	DFN[x] = LOW[x] = ++clk;
	stk[++index] = x;
	vis[x] = 1;
	for(int i = head[x]; ~i; i = e[i].ne) {
		int v = e[i].to;
		if(DFN[v] == 0) {
			Tarjan(v);
			LOW[x] = min(LOW[x],LOW[v]);
		}
		else if(vis[v]) LOW[x] = min(LOW[x],DFN[v]);
	}
	if(DFN[x] == LOW[x]) {
		scc++;
		while(1) {
			int tmp = stk[index];index--;
			vis[tmp]=0;
			col[tmp] = scc;
			if(val[tmp] > 0) VAL[scc] += val[tmp];
			if(tmp == x) break;
		}
	}
}
void dfs(int cur,int rt) {
	if(VIS[cur]) return;
	VIS[cur] = 1;
	for(int i = HEAD[cur]; ~i; i = E[i].ne) {
		int v = E[i].to;
		if(v == rt) continue;
		dfs(v,cur);
		DIS[cur] = max(DIS[cur],DIS[v]);
	}
	DIS[cur] += VAL[cur];
}
int main()
{
	while(~scanf("%d%d",&n,&m)) {
		init();
		for(int i = 1; i<=n; i++) scanf("%d",val+i);
		for(int u,v,i = 1; i<=m; i++) {
			scanf("%d%d",&u,&v);u++,v++;
			add(u,v);
		}
		for(int i = 1; i<=n; i++) {
			if(DFN[i] == 0) Tarjan(i); 
		}
		for(int i = 1; i<=scc; i++) HEAD[i] = -1,ss[i].clear();
		for(int i = 1; i<=tot; i++) {
			int u = e[i].fr;int v = e[i].to;
			u = col[u],v = col[v];
			if(u == v) continue; 
			if(ss[u].find(v) == ss[u].end()) {
				ADD(u,v),IN[v]++;
				ss[u].insert(v);
			}
		}
		int cnt = 0;
		for(int i = 1; i<=scc; i++) {
			if(IN[i] == 0) TMP[++cnt] = i;
		}
		for(int i = 1; i<=cnt; i++) {
			dfs(TMP[i],-1);
		}
		int ans = 0;
		for(int i = 1; i<=cnt; i++) {
			ans = max(ans,DIS[TMP[i]]);
		}
		printf("%d\n",ans);
	}
	return 0 ;
}