【建图+spfa算法】transaction transaction transaction HDU - 6201

以你之姓@ 2022-06-08 01:23 134阅读 0赞

Think:  
1知识点：建图+spfa算法  
2题意：选择一个城市购买一本书，到达另一个城市(或者当前城市)出售这本书，从一个城市到达另一个城市需要支付路费，所有城市构成一个完全图。可以以任何城市作为出发点，询问可以获得的最大利润。  
3方法：增加两个点，分别作为起点和终点，起点与\[1, n\]的点连边，边权为负的点权(表示购买这本书之后剩下的金币)，\[1, n\]的点与终点连边，边权为正的点权(表示出售这本书之后剩下的金币)，然后根据输入的边的关系通过前向星建立双向图，然后通过spfa算法跑最长路

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int N = 101400;
    
    struct Edge{
        int v, w;
        int next;
    }edge[N<<2];
    
    int cnt, head[N], vis[N], dis[N];
    
    void Init();
    void add_edge(int u, int v, int w);
    void spfa(int s);
    
    int main(){
        int T, n, i, u, v, w;
        scanf("%d", &T);
        while(T--){
            Init();
            scanf("%d", &n);
            for(i = 1; i <= n; i++){
                scanf("%d", &w);
                add_edge(0, i, -w);
                add_edge(i, n+1, w);
            }
            for(i = 0; i < n-1; i++){
                scanf("%d %d %d", &u, &v, &w);
                add_edge(u, v, -w);
                add_edge(v, u, -w);
            }
            spfa(0);
            printf("%d\n", dis[n+1]);
        }
        return 0;
    }
    void Init(){
        cnt = 0;
        memset(head, -1, sizeof(head));
    }
    void add_edge(int u, int v, int w){
        edge[cnt].v = v;
        edge[cnt].w = w;
        edge[cnt].next = head[u];
        head[u] = cnt++;
    }
    void spfa(int s){
        queue <int> q;
        while(!q.empty()){
            q.pop();
        }
        memset(vis, 0, sizeof(vis));
        memset(dis, -inf, sizeof(dis));
        vis[s] = 1, dis[s] = 0;
        q.push(s);
        while(!q.empty()){
            int u = q.front();
            q.pop();
            vis[u] = 0;
            for(int i = head[u]; ~i; i = edge[i].next){
                int v = edge[i].v;
                int w = edge[i].w;
                if(dis[v] < dis[u] + w){
                    dis[v] = dis[u] + w;
                    if(!vis[v]){
                        vis[v] = 1;
                        q.push(v);
                    }
                }
            }
        }
    }

[vjudge]: https://vjudge.net/problem/HDU-6201