| Time Limit: 1000MS | Memory Limit: 131072K | |
| Total Submissions: 1822 | Accepted: 599 |
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.
强连通+DP
题目大意：圣诞节要到了，flymouse要给他的队友们送去礼物，，n个队友住在n个不同的房子里，每个队友住的地方都有一个comfort index （positive or negative）;
他每给一个队友送去礼物，都将得到该队友的comfort index ，问最后他能获得的maximized sum of accumulated comfort indices；
不过题目还有其他的要求：follow directed paths to visit one room after another and give out gifts en passant until he could reach no more unvisited rooms。
思路：根据题目要求，可以先进行缩点，因为一个强连通分量里面的所有点，如果能访问其中一个那这个分量里面的所有点都能访问到， 题目要求最大，所以只访问权值为正的点。
缩点之后的每个点都有一个非负的权值。
1. 再重新建图，从入读为0的点开始先下访问，找到最大值。
2. 建立反向图，下面就利用拓扑排序的思想。
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<queue>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define INF 1<<29
#define clr(ttt,t) memset(ttt,t,sizeof(ttt))
#define N 30005
#define M 150005
int n,m,a,b,v,cur;
struct node{
int from,next,to;
}edge1[M],edge2[M],edge[M];
int tol1,tol2,tol;
int Tcnt,Bcnt,Max;
int val[N],T[N],V[N];
int Belong[N],DP[N],in[N];
int head[N],head1[N],head2[N];
int visit1[N],visit2[N],visit[N];
queue<int>S;
void Add(int a,int b){
edge1[tol1].from=a;edge1[tol1].to=b;
edge1[tol1].next=head1[a];
head1[a]=tol1++;
edge2[tol2].from=b;edge2[tol2].to=a;
edge2[tol2].next=head2[b];
head2[b]=tol2++;
}
void add(int a,int b){
edge[tol].from=a;
edge[tol].to=b;
edge[tol].next=head[a];
head[a]=tol++;
}
void dfs1(int i){
int v;
visit1[i]=1;
for(int j=head1[i];j!=-1;j=edge1[j].next){
v=edge1[j].to;
if(!visit1[v]) dfs1(v);
}
T[Tcnt++]=i;
}
void dfs2(int i){
int v;
visit2[i]=1;
Belong[i]=Bcnt;
if(val[i]>0) V[Bcnt]+=val[i];
for(int j=head2[i];j!=-1;j=edge2[j].next){
v=edge2[j].to;
if(!visit2[v]) dfs2(v);
}
}
void find_scc(int n){//(SCC图拓扑顺序的逆序遍历)找连通分量
clr(visit1,0);
clr(visit2,0);
clr(V,0);
Tcnt=Bcnt=0;
for(int i=0;i<n;i++)
if(!visit1[i]) dfs1(i);
for(int i=Tcnt-1;i>=0;i--){
if(!visit2[T[i]]){
dfs2(T[i]);
Bcnt++;
}
}
}
void build(){//重新建图
tol=0;
clr(head,-1);
clr(in,0);
for(int i=0;i<m;i++){
a=edge1[i].from;
b=edge1[i].to;
if(Belong[a]==Belong[b]) continue;
add(Belong[b],Belong[a]);//建立反向边
in[Belong[a]]++;
}
}
void spfa(){
clr(DP,0);
Max=0;
clr(visit,0);
for(int i=0;i<Bcnt;i++){
if(in[i]==0)
S.push(i);
}
while(!S.empty()){
cur=S.front();
S.pop();
for(int j=head[cur];j!=-1;j=edge[j].next){
v=edge[j].to;
if(visit[v]<V[cur]) visit[v]=V[cur];
in[v]--;
if(in[v]==0){
V[v]+=visit[v];
S.push(v);
}
}
if(V[cur]>Max) Max=V[cur];
}
printf("%d\n",Max);
}
void input(){
for(int i=0;i<n;i++)
scanf("%d",&val[i]);
tol1=tol2=0;
clr(head1,-1);
clr(head2,-1);
for(int i=0;i<m;i++){
scanf("%d%d",&a,&b);
Add(a,b);
}
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
input();
find_scc(n);
build();
spfa();
}
return 0;
}