[南海云课堂] [缩点] [拓扑排序] [最短路] 道路与航线

_Cheems · 2023-08-09 16:26:08 · 个人记录

题意

农夫约翰正在一个新的销售区域对他的牛奶销售方案进行调查。

他想把牛奶送到 T 个城镇，编号为 1∼T。

这些城镇之间通过 R 条道路 (编号为 1 到 R) 和 P 条航线 (编号为 1 到 P) 连接。

每条道路 i 或者航线 i 连接城镇 A_i 到 B_i，花费为 C_i。

对于道路，0≤Ci≤10,000;然而航线的花费很神奇，花费 C_i 可能是负数(−10,000≤Ci≤10,000)。

道路是双向的，可以从 A_i 到 B_i，也可以从 B_i 到 A_i，花费都是 C_i。

然而航线与之不同，只可以从 A_i 到 B_i。

事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策：保证如果有一条航线可以从 A_i 到 B_i，那么保证不可能通过一些道路和航线从 B_i 回到 A_i。

由于约翰的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。

他想找到从发送中心城镇 S 把奶牛送到每个城镇的最便宜的方案。

思路

或许有人靠 \rm{SLF} 优化的 \rm{Dijkstra} 过了，但该做法可被卡成指数级的复杂度，因此这只是个歪解。

• 缩点 + 拓扑排序 + \rm{Dijkstra}

  从性质入手，发现该无向图不存在负环，且只由正权边构成的子图一定是环。

  不妨对每个正环缩点，这样图象就变为了若干条负边连接若干个正环（为了方便将单独点也视为一个正环，这并不影响正确性），显然这个图是 DAG。

  回忆 \rm{Dijkstra} 为何无法处理负权边的情况：因为 \rm{Dijkstra} 基于贪心，需满足无后效性的原则，也就是说已被确定最短路的点不能再被更新了。

  而负权边的存在使得其具有后效性，所以 \rm{Dijkstra} 算法可能无法得到离源点最近的点，所有点的最短路径是不确定的，也就无法得出正确答案。

  而缩点后我们便可对每个正环都跑一遍 \rm{Dijkstra}，利用拓扑排序一层一层向外拓展。

  注意负边也要被算入，这时负边不会使得答案错误。经过上面的分析，我们意识到只要解决后效性带来的影响，那么负权边也是可以处理的。

  显然，遍历一个正环后，该正环中就不会再次加入队列中，正环中所有点的最短路径便确定下来。这便是 DAG 带来的好处。

代码

没必要 \rm {Tarjan} 缩点，由于所正边都是无向边，所以用 \rm {DFS} 染色即可。

#include<bits/stdc++.h>
using namespace std;
#define pir pair<int,int>

const int N=25000+5,M=5e4+5,INF=0x3f3f3f3f;
int n,u,v,r,p,s,head[N],cnt,w,vis[N],d[N];
int head2[N],cnt2,col,rt,f[N];
int pd[N],dis[N];
vector<int>vc[N];
struct edge{
    int v,nxt;
    int w;
}e[2*M],e2[M];
void add(int u,int v,int w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
void add2(int u,int v,int w){
    e2[++cnt2].v=v;
    e2[cnt2].w=w;
    e2[cnt2].nxt=head2[u];
    head2[u]=cnt2;
}
void dfs(int u,int id){
    vis[u]=id;
    vc[id].push_back(u);
    if(u==s){
        rt=id;
    }
    for(int i=head[u]; i;i=e[i].nxt){
        int v=e[i].v;
        if(!vis[v]){
            dfs(v,id);
        }
    }
}
void rs(){
    for(int i=1; i<=n;i++){
        if(!vis[i]){
            dfs(i,++col);
        }
    }
}
void dj(int k){
    priority_queue<pir,vector<pir>,greater<pir>>q;
    for(int i=0; i<vc[k].size();i++){
        if(dis[vc[k][i]]<INF){
            q.push({dis[vc[k][i]],vc[k][i]});
        }
    }
    while(!q.empty()){
        int s=q.top().first;
        int u=q.top().second;
        q.pop();
        if(pd[u]){
            continue;
        }
        pd[u]=1;
        for(int i=head[u]; i;i=e[i].nxt){
            int v=e[i].v,w=e[i].w;
            if(!pd[v]&&s+w<dis[v]){
                dis[v]=s+w;
                q.push({dis[v],v});
            }
        }
        for(int i=head2[u]; i;i=e2[i].nxt){
            int v=e2[i].v,w=e2[i].w;
            dis[v]=min(dis[v],dis[u]+w);
        }
    }
}
void topo(){
    queue<int>q;
    for(int i=1; i<=col;i++){
        if(!d[i]){
            q.push(i);
        }
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        dj(u);
        for(int i=0; i<vc[u].size();i++){
            for(int j=head2[vc[u][i]]; j;j=e2[j].nxt){
                int v=e2[j].v;
                d[vis[v]]--;
                if(!d[vis[v]]){
                    q.push(vis[v]);
                }
            }
        }

    }
}

int main(){
    cin>>n>>r>>p>>s;
    for(int i=1; i<=r;i++){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    } 
    rs();
    memset(f,0x3f,sizeof f);    
    memset(dis,0x3f,sizeof dis);
    f[rt]=0;
    for(int i=1; i<=p;i++){
        scanf("%d%d%d",&u,&v,&w);
        add2(u,v,w);
        d[vis[v]]++;
    }
    dis[s]=0;
    topo();
    //缩点、建图，拓扑 
    for(int i=1; i<=n;i++){
        if(dis[i]^INF){
            printf("%d\n",dis[i]);
        }
        else{
            printf("NO PATH\n");
        }   
    } 
    //计算答案
    return 0;
}