提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

POJ3160强连通+spfa最长路（不错）

最长 不错 连通 SPFA
2023-09-11 14:14:00 时间
题意：
      给你一个有向图，每个点上有一个权值，可正可负，然后给你一些链接关系，让你找到一个起点，从起点开始走，走过的边可以在走，但是拿过权值的点就不能再拿了，问最多能拿到多少权值？


思路：
      首先我们考虑一个简单的问题，这个题目的负权值点肯定不拿，对于一个环（应该说是一个强连通分量）来说要拿可以一下全拿走（这个自己黄画画），那么一个环的价值是多少？就是这个强连通分量里所有正权值的和，这样我们一边强连通缩点，缩点之后变成了一个无环的有向图，然后在在上面跑最长路就行了，还有提醒一点，题目说的起点不固定，这个也好处理，我们只要在虚拟出来一个起点，到所有点的权值都是0就行了，这样就能一遍spfa搞定了，千万别跑n遍spfa那样太无脑了。


虽然简单，但感觉这个题目还不错，挺有实际意义的。




#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;
}







相关文章