題意：
? ? ? 給你一個(gè)有向圖，每個(gè)點(diǎn)上有一個(gè)權(quán)值，可正可負(fù)，然后給你一些鏈接關(guān)系，讓你找到一個(gè)起點(diǎn)，從起點(diǎn)開始走，走過(guò)的邊可以在走，但是拿過(guò)權(quán)值的點(diǎn)就不能再拿了，問(wèn)最多能拿到多少權(quán)值？


思路：
? ? ? 首先我們考慮一個(gè)簡(jiǎn)單的問(wèn)題，這個(gè)題目的負(fù)權(quán)值點(diǎn)肯定不拿，對(duì)于一個(gè)環(huán)（應(yīng)該說(shuō)是一個(gè)強(qiáng)連通分量）來(lái)說(shuō)要拿可以一下全拿走（這個(gè)自己黃畫畫），那么一個(gè)環(huán)的價(jià)值是多少？就是這個(gè)強(qiáng)連通分量里所有正權(quán)值的和，這樣我們一邊強(qiáng)連通縮點(diǎn)，縮點(diǎn)之后變成了一個(gè)無(wú)環(huán)的有向圖，然后在在上面跑最長(zhǎng)路就行了，還有提醒一點(diǎn)，題目說(shuō)的起點(diǎn)不固定，這個(gè)也好處理，我們只要在虛擬出來(lái)一個(gè)起點(diǎn)，到所有點(diǎn)的權(quán)值都是0就行了，這樣就能一遍spfa搞定了，千萬(wàn)別跑n遍spfa那樣太無(wú)腦了。


雖然簡(jiǎn)單，但感覺這個(gè)題目還不錯(cuò)，挺有實(shí)際意義的。




#include<stack>
#include<queue>
#include<stdio.h>
#include<string.h>


#define N_node 30000 + 10
#define N_edge 200000 + 50
#define INF 1000000000


using namespace std;


typedef struct
{
? ? int to ,cost ,next;
}STAR;


typedef struct
{
? ? int a ,b;
}EDGE;


EDGE E[N_edge];
STAR E1[N_edge] ,E2[N_edge];
int list1[N_node] ,list2[N_node] ,tot;
int Belong[N_node] ,mark[N_node] ,cont;
int s_x[N_node] ,get[N_node] ,cost[N_node];
stack<int>sk;


void add(int a ,int b ,int c)
{
? ? E1[++tot].to = b;
? ? E1[tot].cost = c;
? ? E1[tot].next = list1[a];
? ? list1[a] = tot;


? ? E2[tot].to = a;
? ? E2[tot].cost = c;
? ? E2[tot].next = list2[b];
? ? list2[b] = tot;
}


void DFS1(int s)
{
? ? mark[s] = 1;
? ? for(int k = list1[s] ;k ;k = E1[k].next)
? ? if(!mark[E1[k].to]) DFS1(E1[k].to);
? ? sk.push(s);
}


void DFS2(int s)
{
? ? mark[s] = 1;
? ? Belong[s] = cont;
? ? for(int k = list2[s] ;k ;k = E2[k].next)
? ? if(!mark[E2[k].to]) DFS2(E2[k].to);
}


void Spfa(int s ,int n)
{
? ? memset(mark ,0 ,sizeof(mark));
? ? for(int i = 0 ;i <= n ;i ++)
? ? s_x[i] = -INF;
? ? queue<int>q;
? ? q.push(s);
? ? mark[s] = 1;
? ? s_x[s] = 0;
? ? while(!q.empty())
? ? {
? ? ? ? int xin ,tou;
? ? ? ? tou = q.front();
? ? ? ? q.pop();
? ? ? ? mark[tou] = 0;
? ? ? ? for(int k = list1[tou] ;k ;k = E1[k].next)
? ? ? ? {
? ? ? ? ? ? xin = E1[k].to;
? ? ? ? ? ? if(s_x[xin] < s_x[tou] + E1[k].cost)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? s_x[xin] = s_x[tou] + E1[k].cost;
? ? ? ? ? ? ? ? if(!mark[xin])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? mark[xin] = 1;
? ? ? ? ? ? ? ? ? ? q.push(xin);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
}


int main ()
{
? ? int n ,m ,i ,a ,b;
? ? while(~scanf("%d %d" ,&n ,&m))
? ? {
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? scanf("%d" ,&cost[i]);
? ? ? ? memset(list1 ,0 ,sizeof(list1));
? ? ? ? memset(list2 ,0 ,sizeof(list2));
? ? ? ? tot = 1;
? ? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? ? {
? ? ? ? ? ? scanf("%d %d" ,&a ,&b);
? ? ? ? ? ? a ++ ,b ++;
? ? ? ? ? ? add(a ,b ,1);
? ? ? ? ? ? E[i].a = a ,E[i].b = b;
? ? ? ? }
? ? ? ? while(!sk.empty()) sk.pop();
? ? ? ? memset(mark ,0 ,sizeof(mark));
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? if(!mark[i]) DFS1(i);
? ? ? ? memset(mark ,0 ,sizeof(mark));
? ? ? ? cont = 0;
? ? ? ? while(!sk.empty())
? ? ? ? {
? ? ? ? ? ? int to = sk.top();
? ? ? ? ? ? sk.pop();
? ? ? ? ? ? if(mark[to]) continue;
? ? ? ? ? ? ++cont;
? ? ? ? ? ? DFS2(to);
? ? ? ? }
? ? ? ? memset(get ,0 ,sizeof(get));
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? if(cost[i] >= 0) get[Belong[i]] += cost[i];
? ? ? ? memset(list1 ,0 ,sizeof(list1));
? ? ? ? memset(list2 ,0 ,sizeof(list2));
? ? ? ? tot = 1;
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? add(0 ,i ,get[i]);
? ? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? ? {
? ? ? ? ? ? a = Belong[E[i].a];
? ? ? ? ? ? b = Belong[E[i].b];
? ? ? ? ? ? if(a == b) continue;
? ? ? ? ? ? add(a ,b ,get[b]);
? ? ? ? }
? ? ? ? Spfa(0 ,n);
? ? ? ? int ans = 0;
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? if(ans < s_x[i]) ans = s_x[i];
? ? ? ? printf("%d\n" ,ans);


? ? }
? ? return 0;
}

總結(jié)

以上是生活随笔為你收集整理的POJ3160强连通+spfa最长路（不错）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。