bzoj2200拓扑排序+最短路+联通块

自己写的不知道哪里wa了，明明和网上的代码差不多。，。

/*

给定一张图，有的边是无向边，有的是有向边，有向边不会出现在环中，且有可能是负权值

现在给定起点s，求出s到其余所有点的最短路长度

任何存在负权边的图都不可以用dij（有向图，无向图，有环图，无环图）

比如(1,2,8),(1,3,10)(3,2,-5),显然1-3的最短路径是5，但是dij求出的就是8

并且spfa超时

利用本题的无向边无 负权，且单向边不会出现在环中，先再每个联通块内求dij，然后用拓扑排序处理联通块之间的距离

先将所有无向边加入图，然后求出所有联通块，将联通块缩点

然后再加入有向边，按拓扑排序进行

算法流程：

    1.把双向边加入图中，确定所有联通块，并染色

    2.把单向边加入图中，确定所有的联通块的出度入度，只有S所在的联通块入度为0情况下才有解

    3.开始拓扑排序，初始队列q中仅有c[S]联通块，同时建立dist数组，dist[s]=0

    4.不断取出队头联通块，在联通块内进行堆优化的dij

        a.把联通块内的所有结点加入堆

        b.从堆中取出d[x]最小的结点，若x已经在最短路集合中，continue

        c.遍历x的所有边(x,y,z),进行松弛

            如果y是联通块内的，并且y被更新，则把y插入堆中

            若y是其他联通块的，那么in[c[y]]--,如果减到了0，就把c[y]加入队尾

*/

#include<bits/stdc++.h>

#include<vector>

#include<queue>

using namespace std;

#define maxn 25005

#define maxm 50005

#define ll long long

struct Edge{int to,nxt,w,flag;}edge[maxm<<];

int head[maxn],tot,in[maxn],t,r,p,s;

void init(){

    memset(head,-,sizeof head);

    tot=;

}

void addedge(int u,int v,int w,int flag){

    edge[tot].to=v;edge[tot].w=w;edge[tot].flag=flag;

    edge[tot].nxt=head[u];head[u]=tot++;

}

int c[maxn],cnt;

vector<int>vec[maxn];

void dfs(int u){//染色

    c[u]=cnt;

    vec[cnt].push_back(u);

    for(int i=head[u];i!=-;i=edge[i].nxt){

        int v=edge[i].to;

        if(c[v]==)dfs(v);

    }

}

int d[maxn],vis[maxn],used[maxn];

int main(){

    while(cin>>t>>r>>p>>s){

        init();

        int u,v,w;

        for(int i=;i<=r;i++){

            scanf("%d%d%d",&u,&v,&w);

            addedge(u,v,w,);

            addedge(v,u,w,);

        }

        memset(c,,sizeof c);

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

            if(!c[i]){

                cnt++;

                vec[cnt].clear();

                dfs(i);

            }

        memset(in,,sizeof in);

        for(int i=;i<=r;i++){

            scanf("%d%d%d",&u,&v,&w);

            addedge(u,v,w,);

            in[c[v]]++;

        }

        memset(d,,sizeof d);

        memset(used,,sizeof used);

        memset(vis,,sizeof vis);

        d[s]=;

        queue<int>q;

        q.push(c[s]);//把s所在联通块入队

        priority_queue<pair<int,int> >pq;

        while(!q.empty()){

            int u=q.front();q.pop();//从队头取出联通块

            for(int i=;i<vec[u].size();i++){

                int v=vec[u][i];

                pq.push(make_pair(-d[v],v));

            }

            while(!pq.empty()){

                int x=pq.top().second;pq.pop();

                if(vis[x])continue;

                vis[x]=;

                for(int i=head[x];i!=-;i=edge[i].nxt){

                    int y=edge[i].to,z=edge[i].w;

                    if(d[y]>d[x]+z){

                        if(c[x]==c[y]){

                            d[y]=d[x]+z;

                            pq.push(make_pair(-d[y],y));

                        }

                    }

                    if(c[x]!=c[y]){

                        d[y]=min(d[x]+z,d[y]);

                        in[c[y]]--;

                        if(in[c[y]]==)

                            q.push(c[y]);

                    }

                }

            }

        }

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

            if(d[i]>0x3f3f3f3f)puts("NO PATH");

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

    }

} 

网上的

#include<bits/stdc++.h>

#define ll long long

#define fo(i,j,n) for(register int i=j; i<=n; ++i)

using namespace std;

const int N = ,M = , INF=0x3f3f3f3f; // M为双向边加单向边

int T,R,P,S,d[N];

int head[N],Next[M],ver[M],edge[M],tot;

bool v[N];

int c[N],totc,deg[N];

queue<int> q; // 联通块的拓扑序

priority_queue<pair<int, int> > Q; // Dij

void add(int x,int y, int z){

    ver[++tot]=y, edge[tot]=z;

    Next[tot]=head[x], head[x]=tot;

}

void dfs(int x){

    for(int i=head[x]; i; i=Next[i]){

        int y = ver[i];

        if(!c[y]){

            c[y]=totc;

            dfs(y);

        }

    }

}

void Dijkstra(){

    while(Q.size()){

        int x = Q.top().second; Q.pop();

        if(v[x])continue;

        v[x] = ;

        for(int i=head[x]; i; i=Next[i]){

            int y = ver[i], wei = edge[i];

            if(d[y] > d[x]+wei){

                d[y] = d[x]+wei;

                if(c[y]==c[x]) Q.push(make_pair(-d[y], y));

            }

            // 对遍历到的点，判断是否不同联通块

            // 联通块入度减少，并且判0

            if(c[x]!=c[y] && !--deg[c[y]])q.push(c[y]);

        }

    }

}

int main(){

    cin>>T>>R>>P>>S;

    int x,y,z;

    fo(i,,R){

        scanf("%d%d%d",&x,&y,&z);

        add(x,y,z); add(y,x,z);

    }

    // 划分联通块

    fo(i,,T){

        if(!c[i]){

            c[i]=++totc;

            dfs(i);

        }

    }

    fo(i,,P){

        scanf("%d%d%d",&x,&y,&z);

        add(x,y,z);

        ++deg[c[y]]; // 联通块的入度

    }

    // 联通块之间进行拓扑排序

    q.push(c[S]); // 先加入起点

    fo(i,,totc)if(!deg[i])q.push(i); // 加入0度的联通块

    // topsort

    memset(d, , sizeof(d)); // 这里最大值不能为0x3f,0x7f对应127

    d[S] = ;

    while(q.size()){

        int i = q.front(); q.pop();

        fo(j,,T)

            if(c[j]==i)

                Q.push(make_pair(-d[j], j)); // 联通块

        Dijkstra();

    }

    fo(i,,T){

        if(d[i]>INF)puts("NO PATH");

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

    }

} 

bzoj2200拓扑排序+最短路+联通块的相关教程结束。