POJ 3160(축소점+spfa 최장거리+dp)

K - 강연통
Time Limit:1000MS     Memory Limit:131072KB     64bit IO Format:%I64d & %I64u
Submit
 
Status
Description
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

2 2
14
21
0 1
1 0

Sample Output

35

Hint
32-bit signed integer type is capable of doing all arithmetic.
 
구야 GG의 제목:
제목:
n개의 점 m줄에 방향이 있는 그림을 정하다
각 점의 점권
질문:
그림에서 얻을 수 있는 최대 점권 (지나간 점에 대해서는 이 점권을 획득할지 여부를 선택할 수 있지만, 점마다 한 번만 획득할 수 있습니다)
시작점은 임의로 할 수 있다.
아이디어:
우리가 유방향도 축소점을 유방향의 축소점 트리로 하면 어떤 강한 연결 블록의 값은 이 연결 블록 아래의 모든 정점 값과
이렇게 하면 우리는 유향무환도를 얻을 수 있다. 분명히 우리가 선택한 출발점은 입도가 0인 점이다. 왜냐하면 모든 입도가 0이 아닌 점은 다른 점에서 걸어올 수 있기 때문이다.
 
그럼 in[i]==0의 점에서 spfa를 뛰고 가장 긴 길을 구합니다. bfs의 과정은 dp와 함께 하면 됩니다.
이 문제는 내가 적어도 20번은 냈는데 생각이 맞았지만 WA, WA는 죽을 때까지 갔다가 마지막에 기사회생했다. 다시 두 번 썼다고 미루면 지나갔다.

/****************************
* author:crazy_  
* date：2014/01/18
* algorithm:tarjan+spfa
* Pro：POJ 3160
***************************/
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>

using namespace std;

#define INF 1<<29
#define eps 1e-8
#define A system("pause")
#define rep(i,h,n) for(int i=(h);i<=(n);i++)
#define ms(a,b) memset((a),(b),sizeof(a))

const int maxn=30000+10;
const int maxm=150000+10;

struct edge
{
	int to,next;
}e[maxm];
int dfn[maxn],low[maxn],belong[maxn],stack[maxn],in[maxn],head1[maxn],head2[maxn],scc,top,index,n,m,cnt;
bool instack[maxn],vis[maxn];
int dp[maxn],sum[maxn],w[maxn];

inline void addedge(int u,int v,int head[])
{
	e[cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt++;
}

inline void tarjan(int u)
{
	int v;
	dfn[u]=low[u]=++index;
	stack[++top]=u,instack[u]=1;
	for(int i=head1[u];~i;i=e[i].next)
	{
		v=e[i].to;
		if(dfn[v]==-1)
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(instack[v])
        low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		scc++;
		do
		{
			v=stack[top--];
			instack[v]=0;
			belong[v]=scc;
			sum[scc]+=w[v];
		}while(u!=v);
	}
}

inline void init()
{
	int u,v;
	scc=index=top=cnt=0;
	ms(dfn,-1),ms(instack,0),ms(head1,-1),ms(head2,-1),ms(sum,0);
	for(int i=1;i<=n;i++)
	{
	    scanf("%d",&w[i]);
	    if(w[i]<0)w[i]=0;
	}
	while(m--)
	{
		scanf("%d%d",&u,&v);
		addedge(u+1,v+1,head1);//   1  ；
	}
	rep(i,1,n) if(dfn[i]==-1) tarjan(i);
}

inline void Rebuild()
{
	int i,j,v;
	ms(in,0);
	rep(u,1,n)
	for(i=head1[u];~i;i=e[i].next)
	{
		v=e[i].to;
		if(belong[u]!=belong[v])
		{
			addedge(belong[u],belong[v],head2);
			in[belong[v]]++;
		}
	}
}

inline int spfa(int s)
{
	queue<int> q;
	ms(vis,0);
	q.push(s),vis[s]=1;
	int res=dp[s]=sum[s];
	while(!q.empty())
	{
		int u=q.front();
		q.pop(),vis[u]=0;
		for(int i=head2[u];~i;i=e[i].next)
		{
			int v=e[i].to;
			dp[v]=max(dp[v],dp[u]+sum[v]);
			res=max(res,dp[v]);
			if(!vis[v])q.push(v),vis[v]=1;
		}
	}
	return res;
}

int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		init();
		int i,ans=0;
		ms(dp,0);
		Rebuild();//       ；
		for(i=1;i<=scc;i++)if(in[i]==0)ans=max(ans,spfa(i));//    0      spfa      ；
		printf("%d
",ans);
	}
	return 0;
}