bzoj 2200: [Usaco2011 Jan]道路和航线——拓扑+dijkstra

Description

Farmer John正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到T个城镇 (1 <= T <= 25,000)，编号为1T。这些城镇之间通过R条道路 (1 <= R <= 50,000，编号为1到R) 和P条航线 (1 <= P <= 50,000，编号为1到P) 连接。每条道路i或者航线i连接城镇A_i (1 <= A_i <= T)到B_i (1 <= B_i <= T)，花费为C_i。对于道路，0 <= C_i <= 10,000;然而航线的花费很神奇，花费C_i可能是负数(-10,000 <= C_i <= 10,000)。道路是双向的，可以从A_i到B_i，也可以从B_i到A_i，花费都是C_i。然而航线与之不同，只可以从A_i到B_i。事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策保证：如果有一条航线可以从A_i到B_i，那么保证不可能通过一些道路和航线从B_i回到A_i。由于FJ的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。他想找到从发送中心城镇S(1 <= S <= T) 把奶牛送到每个城镇的最便宜的方案，或者知道这是不可能的。

Input

* 第1行：四个空格隔开的整数: T, R, P, and S * 第2到R+1行：三个空格隔开的整数（表示一条道路）：A_i, B_i 和 C_i * 第R+2到R+P+1行：三个空格隔开的整数（表示一条航线）：A_i, B_i 和 C_i

Output

* 第1到T行：从S到达城镇i的最小花费，如果不存在输出"NO PATH"。

Sample Input

6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10

样例输入解释：

一共六个城镇。在1-2，3-4，5-6之间有道路，花费分别是5，5，10。同时有三条航线：3->5，
4->6和1->3，花费分别是-100，-100，-10。FJ的中心城镇在城镇4。

Sample Output

NO PATH
NO PATH
5
0
-95
-100

样例输出解释：

FJ的奶牛从4号城镇开始，可以通过道路到达3号城镇。然后他们会通过航线达到5和6号城镇。
但是不可能到达1和2号城镇。
————————————————————————————————————
这道题spfa+slf优化之后就可以AC了不过很慢QAQ其实是属于强行水过QAQ

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

const int M=3e4+,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

bool f=false;

int n,nr,np,S;

int first[M],cnt;

struct node{int to,next,w;}e[*M];

void ins(int a,int b,int w){e[++cnt]=(node){b,first[a],w}; first[a]=cnt;}

void insert(int a,int b,int w){ins(a,b,w); ins(b,a,w);}

int dis[M],vis[M];

int q[M],head,tail=;

void spfa(){

    memset(dis,0x3f,sizeof(dis));

    dis[S]=; vis[S]=;

    q[head]=S;

    while(head!=tail){

        int x=q[head++]; if(head>M) head=;

        for(int i=first[x];i;i=e[i].next){

            int now=e[i].to;

            if(dis[now]>dis[x]+e[i].w){

                dis[now]=dis[x]+e[i].w;

                if(!vis[now]){

                    vis[now]=;

                    if(dis[now]<=dis[q[head]]){

                        head--;

                        if(head<) head=M;

                        q[head]=now;

                    }

                    else{q[tail++]=now; if(tail>M) tail=;}

                }

            }

        }

        vis[x]=;

    }

    for(int i=;i<=n;i++)

        if(dis[i]>=inf) printf("NO PATH\n");

        else printf("%d\n",dis[i]);

}

int main(){

    int x,y,w;

    n=read(); nr=read(); np=read(); S=read();

    for(int i=;i<=nr;i++) x=read(),y=read(),w=read(),insert(x,y,w);

    for(int i=;i<=np;i++) x=read(),y=read(),w=read(),ins(x,y,w);

    spfa();

    return ;

}

当然正解是dijkstra +一波拓扑排序

因为负权边是有向且不存在能经过负权边的环所以我们可以忽略航道

把图变成一个一个的颜色块

这样我们可以单独处理每个块的信息

至于为什么要拓扑给个图吧

从S开始拓扑嘛必须是所有指向一个块的前块都处理完才能处理当前块

当然像图中的红色点如果正常的拓扑S所在的联通块入度就不为0了

而且实际上这两个块应该是无解的我们要先处理这种情况

其实从S 开始dfs一波标记一下就好了

然后根据拓扑序每个块dijkstra就可以了（细节有点多QAQ

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

const int M=3e4+,inf=0x3f3f3f3f;

char buf[*M],*ptr=buf-;

int read(){

    int ans=,f=,c=*++ptr;

    while(c<''||c>''){if(c=='-') f=-; c=*++ptr;}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=*++ptr;}

    return ans*f;

}

bool flag=false;

int n,nr,np,S;

int first[M],cnt;

struct node{int to,next,w;}e[*M];

void ins(int a,int b,int w){e[++cnt]=(node){b,first[a],w}; first[a]=cnt;}

void insert(int a,int b,int w){ins(a,b,w); ins(b,a,w);}

int color[M],hc;

void dfs(int x){

    color[x]=hc;

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        if(!color[now]) dfs(now);

    }

}

int sum,star[M];

struct pos{int from,to,next,w;}q[*M];

void insq(int a,int b,int w){q[++sum]=(pos){a,b,star[a],w}; star[a]=sum;}

int f[M],vis[M];

void find(int x){

    vis[x]=f[color[x]]=n+;

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        if(!vis[now]) find(now);

    }

}

int k,dis[M],wh[M],mark[*M];

struct QAQ{

    int d,id;

    bool operator <(const QAQ& x)const{return x.d<d;}

};

std::priority_queue<QAQ>qu[M];

std::queue<int>Q;

int in[M];

void find_w(int x){

    vis[x]=k;

    for(int i=star[x];i;i=q[i].next){

        int now=color[q[i].to];

        dis[q[i].to]=std::min(dis[q[i].to],dis[x]+q[i].w);

        qu[now].push((QAQ){dis[q[i].to],q[i].to});

        if(!--in[now]) Q.push(now);

    }

    for(int i=first[x];i;i=e[i].next)if(!mark[i]){

        int now=e[i].to;

        if(vis[now]!=k) find_w(now);

    }

}

int main(){

    fread(buf,,sizeof(buf),stdin);

    int x,y,w;

    n=read(); nr=read(); np=read(); S=read();

    for(int i=;i<=nr;i++) x=read(),y=read(),w=read(),insert(x,y,w);

    for(int i=;i<=n;i++)if(!color[i]) hc++,wh[hc]=i,dfs(i);

    //for(int i=1;i<=n;i++) printf("[%d] ",color[i]); puts("");

    for(int i=;i<=np;i++) x=read(),y=read(),w=read(),ins(x,y,w),mark[cnt]=,insq(x,y,w);

    find(S); //for(int i=1;i<=hc;i++) printf("[%d]\n",f[i]);

    memset(dis,0x3f,sizeof(dis)); dis[S]=;

    for(int i=;i<=sum;i++) if(f[color[q[i].from]]&&f[color[q[i].to]]) in[color[q[i].to]]++;

    //for(int i=1;i<=hc;i++) printf("[%d] ",in[i]); puts("");

    Q.push(color[S]); qu[color[S]].push((QAQ){,S});

    while(!Q.empty()){

        int x=Q.front(); Q.pop(); k++;

        while(!qu[x].empty()){

            QAQ p=qu[x].top(); qu[x].pop();

            if(dis[p.id]<p.d) continue;

            for(int i=first[p.id];i;i=e[i].next)if(!mark[i]){

                int now=e[i].to;

                if(dis[now]>dis[p.id]+e[i].w) dis[now]=dis[p.id]+e[i].w,qu[x].push((QAQ){dis[now],now});

            }

        }

        //printf("[%d]\n",x);

        find_w(wh[x]);

    }

    for(int i=;i<=n;i++)

        if(dis[i]>=inf) printf("NO PATH\n");

        else printf("%d\n",dis[i]);

    return ;

}