Codeforces 545E. Paths and Trees[最短路+贪心]

[题目大意]
　题目将从某点出发的所有最短路方案中,选择边权和最小的最短路方案,称为最短生成树。

　题目要求一颗最短生成树，输出总边权和与选取边的编号。
[题意分析]
　比如下面的数据:
　5 5
　1 2 2
　2 3 2
　3 4 16
　1 5 18
　4 5 2
　1

　这个图对于从 1 出发,有两种最短路。

这种最短路方案中 dis[2]=2，dis[3]=4，dis[4]=20，dis[5]=18。边权总和 Sum=44

但如果这样选边，1点到各点的距离依然为最短路，但Sum降为了24。

那么如何选择到最优的方案呢。由于最短路方案构成的图一定是一棵树，所以我们可以将除源点外的所有顶点搞一个贪心。

改写dijkstra算法(c[]数组用来存取与该点连接的边的cost，s[]数组用来存取与该点连接的边的编号):

const ll inf=0x7fffffffffffff;

struct Edge{

    int to,cost,id;

    Edge(int T,int C,int D):to(T),cost(C),id(D){}

};

typedef pair<long long,int> P;

vector<Edge>G[];

ll d[],c[];

void dij(int u){

    fill(d,d+n+,inf);

    fill(c,c+n+,inf);

    d[u]=;

    priority_queue<P,vector<P>,greater<P>> q;

    q.push(P(d[u],u));

    while(!q.empty()){

        P p=q.top();

        q.pop();

        int v=p.second;

        if(d[v]<p.first) continue;

        for(int i=;i<G[v].size();i++){

            Edge e=G[v][i];

            if(d[e.to]>d[v]+e.cost){

                d[e.to]=d[v]+e.cost;

                s[e.to]=e.id;

                c[e.to]=e.cost;

                q.push(P(d[e.to],e.to));

            }

            else if(d[e.to]==d[v]+e.cost&&c[e.to]>e.cost){

                s[e.to]=e.id;

                c[e.to]=e.cost;

            }

        }

    }

}

当有多条路通往一个顶点，且这两种路线cost相同时，我们可以将 通往该顶点的边 和 该顶点 绑定起来，我们希望每个顶点都能绑定合法的（不影响最短路的）且权值最小的边。

在dijkstra算法中我们每次挑选优先队列中权值最小的路。当碰上两条路cost相等的时候，我们选择与下一个点连接且边权最小的那一条边与下一个点绑定(Cost[nextV]=e.cost)。

* 由于最短路中从源点通往每个点的路可以组成一颗树且点只与从源点走向该点的边相绑定，所以一个点一定可以绑定一条边。

选取完毕后，我们只需要遍历 c[] 数组求出总花费，再遍历 s[] 数组输出每个点绑定的边的编号即可。

***Code:

 #include<bits/stdc++.h>

 #define ll long long

 using namespace std;

 int m,n,s[];

 const ll inf=0x7fffffffffffff;

 struct Edge{

     int to,cost,id;

     Edge(int T,int C,int D):to(T),cost(C),id(D){}

 };

 typedef pair<long long,int> P;

 vector<Edge>G[];

 ll d[],c[];

 void dij(int u){

     fill(d,d+n+,inf);

     fill(c,c+n+,inf);

     d[u]=;

     priority_queue<P,vector<P>,greater<P>> q;

     q.push(P(d[u],u));

     while(!q.empty()){

         P p=q.top();

         q.pop();

         int v=p.second;

         if(d[v]<p.first) continue;

         for(int i=;i<G[v].size();i++){

             Edge e=G[v][i];

             if(d[e.to]>d[v]+e.cost){

                 d[e.to]=d[v]+e.cost;

                 s[e.to]=e.id;

                 c[e.to]=e.cost;

                 q.push(P(d[e.to],e.to));

             }

             else if(d[e.to]==d[v]+e.cost&&c[e.to]>e.cost){

                 s[e.to]=e.id;

                 c[e.to]=e.cost;

             }

         }

     }

 }

 int main(){

     int u,v,co;

     scanf("%d%d",&n,&m);

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

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

         G[u].push_back(Edge(v,co,i));

         G[v].push_back(Edge(u,co,i));

     }

     scanf("%d",&u);

     dij(u);

     ll sum=;

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

         if(i!=u) sum+=c[i];

     }

     cout<<sum<<endl;

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

         if(i!=u) cout<<s[i]<<' ';

     }

    return ;

 }

2017/7/13

巴特西

Codeforces 545E. Paths and Trees[最短路+贪心]

最新文章

热门文章