[原创]POJ 3460 Father Christmas flymouse [强连通缩点+最长路]【图论】

2017-06-08 20:15:31 Tabris_ 阅读数：214

博客爬取于2020-06-14 22:40:03
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72934503

题目链接：http://poj.org/problem?id=3160
————————————————————————————————————————
Father Christmas flymouse
Time Limit: 1000MS Memory Limit: 131072K
Total Submissions: 3483 Accepted: 1187
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.
————————————————————————————————————————

题目大意：
就是给你N个点，M条有向边，每个点一个权值，走过这个点可以取走这个价值，也可以留下，让你找一条路使得能获得的权值最大。

解题思路；
首先这个权值最大 很好处理，权值为正就取，负的就不取，为了方便，将负值全部变为0；

然后考虑到可能存在有向环，所以要缩点做，

缩点后从新建图，然后建一个超级源点，跑最长路就好了

最长路用SPFA即可

附本题代码
————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
# include<stdio.h>
# include<iostream>
# include<vector>
# include<algorithm>
# include<queue>
typedef long long int LL;
using namespace std;

const int N   = 5555+7;
const int MOD = 1e9+7;
const int INF = (~(1<<31))>>1;
//const double Pi = acos(-1.0);

# define abs(x) ((x)>0?(x):-(x))

/****************************************************/


vector<int>G[N];
vector<pair<int,int> >G2[N];

int low[N],dfn[N],w[N],d[N];
int vis[N],val[N];
int color[N],cnt,tot;
int mystack[N],len;

void dfs(int u){vis[u]=1;
    dfn[u]=low[u]=++cnt;
    mystack[++len]=u;
    int gz=G[u].size();
    for(int to,i=0;i<gz;i++){
        to=G[u][i];
        if(vis[to]==0) dfs(to);
        if(vis[to]==1) low[u]=min(low[u],low[to]);
    }

    if(dfn[u]==low[u]){
        ++tot;
        do{
            val[tot]+=w[mystack[len]];
            color[mystack[len]]=tot;
            vis[mystack[len]]=2;
        }while(mystack[len--]!=u);
    }
}

int n,m;
int main(){

    while(~scanf("%d%d",&n,&m)){
        cnt=tot=len=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&w[i]);
            if(w[i]<0) w[i]=0;
        }

        for(int i=1,u,v;i<=m;i++){
            scanf("%d%d",&u,&v);
            G[u+1].push_back(v+1);
        }

        for(int i=1;i<=n;i++)if(vis[i]==0)dfs(i);
        for(int i=1;i<=tot;i++) G2[0].push_back(make_pair(val[i],i));

        for(int i=1,gz;i<=n;i++){vis[i]=0,d[i]=0;
            gz=G[i].size();
            for(int j=0,to;j<gz;j++){
                to=G[i][j];
                if(color[i]!=color[to])
                    G2[color[i]].push_back(make_pair(val[color[to]],color[to]));
            }
        }

        queue<int> q;
        q.push(0);
        d[0]=0;vis[0]=1;
        while(!q.empty()){
            int u=q.front();q.pop();
            vis[u]=0;
            int gz=G2[u].size();
            for(int i=0,to;i<gz;i++){
                to=G2[u][i].second;
                if(d[to]<d[u]+G2[u][i].first){
                    d[to]=d[u]+G2[u][i].first;
                    if(vis[to]==1)continue;
                    vis[to]=1; q.push(to);
                }
            }
        }

        int ans = 0;
        for(int i=1;i<=tot;i++)ans=max(ans,d[i]);

        printf("%d\n",ans);
        for(int i=0;i<=n;i++) G[i].clear(),vis[i]=color[i]=val[i]=0;
        for(int i=0;i<=n;i++) G2[i].clear();
    }
    return 0;
}