一道图论大杂烩题的分析

今天“杭电杯”出了场图论大杂烩题--1002 Link with Running（题目链接：Problem - 7175 (hdu.edu.cn)），整体上用了最短路图，targan还有最长路，都是我不太懂的知识点（貌似我好像只会最短路），所以正好就这题来给它们挨个学习加巩固一遍。

这道题的主要思路便是就energy求一遍最短路，并得出相应的最短路图，同时我们注意到一条边的energy可能为0，所以生成的图里是有环的可能的，所以说用targan整出个无环图，进而再用最长路来求取最大的physical fitness，从而得到两个答案。

1.最短路图

最短路相信大家都了解，最短路图实则就是所有最短路构成的图。

实际上我们需要做的便是对每一条边判断它是否在图中，而这个判断也很简单。事实上，先跑一遍dijkstra从而获得dis数组（表示每一个点到初始点s的最短距离），紧接着对于每一条边，设其由u到v并且边权为w，则其在图中的充要条件便是：

\(dis[u]+w=dis[v]\)

必要性显然，充分性的话利用归纳搜索一次也可以显然证明。也就是说，我们这样便能找到一张图，其中不管怎么走到一个点，所走的路径都是那个点的最短路径，这便使我们可以接下来在这张图里找最大路。

看了题目和题解的同学会发现，在原题中给定了起点和终点，所以我们只要这两点间的最短路构成的图即可，但是题解的做法实则只考虑到起点，而未将终点纳入限制。什么意思呢，就是对于点u，如果说起点s可以到达u，但是没有一条s到终点t的路径里包含u，那么在构图的时候我们实则可以忽略掉u了，而下面的解法则还是考虑了。所以如果想避免其，可以弄一个反向图，以t为起点来一个dijkstra，整出个dis2（原来的叫做dis1），那么边要满足：\(dis1[u]+w+dis2[v]==dis1[t]\)

时才能纳入便可以了。（此想法源自博客(67条消息) 最短路图(dijkistra)_简单666的博客-CSDN博客_最短路图）

以下为题解中的代码：

Show Code

namespace GetSpg{
    ll dis[MN+5];
    vector<Edge> e[MN+5];
    void clear(int n){
        for(int i=1;i<=n;i++){
            e[i].clear();
        }
    }
    void addEdge(int u,int v,int w1,int w2){
        e[u].push_back({v,w1,w2});
    }
    void dijkstra(int n,int S){
        using pii = std::pair<ll,int>;
        priority_queue<pii,vector<pii>,greater<pii>> pq;
        for(int i=1;i<=n;i++){
            dis[i] = INF;
        }
        pq.push({dis[S]=0,S});
        while(!pq.empty()){
            int u = pq.top().second;
            ll d = pq.top().first;
            pq.pop();
            if(d!=dis[u]) continue;
            for(Edge edge:e[u]){
                int v = edge.v;
                int w = edge.w1;
                if(dis[u]+w<dis[v]){
                    dis[v] = dis[u]+w;
                    pq.push({dis[v],v});
                }
            }
        }
    }
    void solve(int n,function<void(int,int,int,int)> addEdge){
        dijkstra(n,1);
        for(int u=1;u<=n;u++){
            if(dis[u]==INF) continue;
            for(Edge edge:e[u]){
                if(dis[u]+edge.w1==dis[edge.v]){
                    addEdge(u,edge.v,edge.w1,edge.w2);
                }
            }
        }
    }
}

2.targan缩点

targan的目的主要是找出一个图中的强连通分量，再将每一个强连通分量对应一个点构成一个新图，这样我们便能得到一个有向无环图。关于targan的原理本人道行浅薄暂时不做解释，日后可能会专门发一篇文章。

以下为题解中代码：

Show Code

namespace GetDag{
    vector<Edge> e[MN+5];
    stack<int> s;
    bool ins[MN+5];
    int low[MN+5],dfn[MN+5],scc[MN+5];
    int dfnCnt=0,sccCnt=0;
    void clear(int n){
        for(int i=1;i<=n;i++){
            e[i].clear();
            ins[i] = false;
            dfn[i] = low[i] = scc[i] = 0;
        }
        dfnCnt = 0;
        sccCnt = 0;
        while(!s.empty()) s.pop();
    }
    void addEdge(int u,int v,int w1,int w2){
        e[u].push_back({v,w1,w2});
    }
    void tarjan(int u){
        dfn[u] = ++dfnCnt;
        low[u] = dfn[u];
        s.push(u);
        ins[u] = true;
        for(Edge edge:e[u]){
            int v = edge.v;
            if(dfn[v]){
                if(ins[v]){
                    low[u] = min(low[u],dfn[v]);
                }
            }else{
                tarjan(v);
                low[u] = min(low[u],low[v]);
            }
        }
        if(low[u]==dfn[u]){
            int v;
            ++sccCnt;
            do{
                v = s.top();
                s.pop();
                ins[v] = false;
                scc[v] = sccCnt;
            }while(u!=v);
        }
    }
    void solve(int& n,function<void(int,int,int,int)> addEdge,bool isLoop[]){
        for(int i=1;i<=n;i++){
            if(!dfn[i]){
                tarjan(i);
            }
        }
        for(int u=1;u<=n;u++){
            for(Edge edge:e[u]){
                int v = edge.v;
                if(scc[u]==scc[v]){
                    if(edge.w2>0){
                        isLoop[scc[u]] = true;
                    }
                }else{
                    addEdge(scc[u],scc[edge.v],edge.w1,edge.w2);
                }
            }
        }
    }
}

3.最大路

其实最大路的思想类似于求最小路，但为什么不能直接搬过来呢，因为如果说按照dijkstra的思路，每次选出一个最长的路径来，同时把此路径对应点v标记并用其更新，我们会惊奇的发现，这样是不对的，因为这或许不是v的最长路径。原因的话可以看看右边这张图：

可以看到如果用求最小路的思路，会得到b的最长路径值为2，而实际上应该为4（换句话来讲，如果说求最短路的过程中出现了负值的边，我们会发现这个dijkstra算法也是不行的）。

故为了实现其，我们必须要转换往队列里加点的条件，其不再是dis受到更新，而是所有经过它的边此刻都已使用过（当所有经过它的边都考虑到了，这时它的dis必然就是最大值），当然，这个思路能行有一个条件，那便是这个图得是有向无环的，因此上一步的targan便很关键了。相关的实现可以看看题解中的代码。

听别人说这个思路很像是拓扑，笔者太弱了不太清楚拓扑，以后可能会更新相关内容。

附上题解中的代码：

Show Code

namespace GetLp{
    int din[MN+5];
    bool isLoop[MN+5];
    vector<Edge> e[MN+5];
    struct Dis{
        ll d;
        Dis(ll d=0){
            this->d = d;
        }
        Dis operator + (const Dis& that)const{
            if(d==-INF||that.d==-INF) return Dis(-INF);
            if(d==INF||that.d==INF) return Dis(INF);
            return Dis(d+that.d);
        }
        bool operator < (const Dis& that)const{
            return this->d < that.d;
        }
    };
    Dis f[MN+5];
    void clear(int n){
        for(int i=1;i<=n;i++){
            din[i] = 0;
            isLoop[i] = false;
            e[i].clear();
        }
    }
    void addEdge(int u,int v,int w1,int w2){
        e[u].push_back({v,w1,w2});
        din[v]++;
    }
    void solve(int n,int S){
        for(int i=1;i<=n;i++){
            f[i] = -INF;
        }
        f[S] = 0;
        queue<int> q;
        for(int i=1;i<=n;i++){
            if(din[i]==0) q.push(i);
        }
        while(!q.empty()){
            int u = q.front();
            q.pop();
            if(isLoop[u]) f[u] = f[u] +INF;
            for(Edge edge:e[u]){
                int v = edge.v;
                int w = edge.w2;
                f[v] = max(f[v],f[u]+w);
                if(--din[v]==0){
                    q.push(v);
                }
            }
        }
    }
}