LA4080最短路树的应用

  1 /*LA4080最短路树的应用
  2 这道题的目的就是让人去合理运用最短路算法中的信息？
  3 求两两点之间的距离之和，一般让人去想到Floyd,或者n次的DIJ，但是Floyd算法虽然精简，但是可用的信息比较少，一次就要n^3的复杂度，
  4 如果直接这样做，肯定会超时，然而dij就灵活的多，有的信息能重复使用。
  5 思想：
  6 1、从每个源点出发，会产生一个最短路树，即是除了根节点之外，每个节点只有一个前驱，这个符合dij路径的唯一性
  7 2、对于一条边，如果这条边不在这条树上，肯定不会影响这棵树根节点i的dij距离和
  8 3、如果在树上，则对于树的根结点，要重新算一次dij
  9 细节：因为我们在计算的时候，只是模拟的把其中的边删除，所以一定不要影响原图的信息
 10 */
 11 #include<iostream>
 12 #include<string.h>
 13 #include<stdio.h>
 14 #include<stdlib.h>
 15 #include<cmath>
 16 #include<algorithm>
 17 #include<queue>
 18 #include<stack>
 19 #include<set>
 20 #include<map>
 21 #define maxn 110
 22 #define maxe 2100
 23 #define INF 100000000
 24 using namespace std;
 25 int N,M,L;
 26 int C,NC;
 27 //set<int>Tree[maxn];//存储没课最短路树上的所有边
 28 bool Tree[maxn][maxe];
 29 int tot[maxn];//每个节点的单源最短距离之和
 30 int nextint(){int x;scanf("%d",&x);return x;}
 31 struct Edge
 32 {
 33     int u,v,dis;
 34 };
 35 struct Node
 36 {
 37     int d,u;
 38     bool operator<(const Node &x)const{
 39         return d>x.d;
 40     }
 41 };
 42 struct Dijkstra
 43 {
 44     int n,m;
 45     vector<Edge>edge;
 46     vector<int>G[maxn];
 47     bool vis[maxn];
 48     int d[maxn],p[maxn];
 49 
 50     void init(int n)
 51     {
 52         this->n=n;
 53         edge.clear();
 54         for(int i=0;i<=n;i++) G[i].clear();
 55     }
 56 
 57     void add(int u,int v,int c){
 58         edge.push_back((Edge){u,v,c});
 59         m=edge.size();
 60         G[u].push_back(m-1);
 61     }
 62 
 63     int dij(int s,int earse)//源点、应该删除的边earse和earse+1
 64     {
 65         memset(vis,0,sizeof(vis));
 66         for(int i=0;i<=n;i++) d[i]=INF;
 67         d[s]=0;
 68         priority_queue<Node>Q;
 69         Q.push((Node){0,s});
 70         while(!Q.empty()){
 71             Node x=Q.top();Q.pop();
 72             int u=x.u;
 73             if (vis[u]) continue;
 74             vis[u]=true;
 75             for(int i=0;i<G[u].size();i++)
 76             {
 77                 if (earse>=0&& ( G[u][i]==earse || G[u][i]==earse+1)) continue;//开始把变量弄错了啊
 78                 Edge &e=edge[G[u][i]];
 79                 if (d[e.v]>d[u]+e.dis){
 80                     d[e.v]=d[u]+e.dis;
 81                     p[e.v]=G[u][i];
 82                     Q.push((Node){d[e.v],e.v});
 83                 }
 84             }
 85         }
 86         if (earse>=0)
 87         {
 88             int tot=0;
 89             for(int i=1;i<=n;i++)
 90             {
 91                 if (i==s) continue;
 92                 if(d[i]<INF) tot+=d[i];else tot+=L;
 93             }
 94             return tot;
 95         }
 96         else
 97         {
 98             tot[s]=0;
 99             for(int i=1;i<=n;i++)
100             {
101                 if (i==s) continue;
102                 if(d[i]<INF) tot[s]+=d[i];else tot[s]+=L;
103             }
104             for(int i=1;i<=n;i++)//树上有n-1条边
105             {
106                 if(i==s) continue;
107                 Tree[s][p[i]]=true;
108             }
109             return -1;
110         }
111     }
112 }Dij;
113 void read()
114 {
115     Dij.init(N);
116     for(int i=0;i<M;i++)
117     {
118         int u,v,d;
119         u=nextint();v=nextint();d=nextint();
120         Dij.add(u,v,d);
121         Dij.add(v,u,d);
122     }
123 }
124 void init_c()//每个点dij，记录tree，和tot[i]
125 {
126     memset(Tree,0,sizeof(Tree));
127     C=0;
128     for(int i=1;i<=N;i++) {Dij.dij(i,-2);C+=tot[i];}//-2：暂时没有要删除的边
129 }
130 void solve()
131 {
132     NC=0;
133     for(int i=0;i<2*M;i+=2)//枚举每条边,记得是无向图，一条边，存储了两个
134     {
135         int T=0;
136         for(int j=1;j<=N;j++)
137         {
138             if (Tree[j][i] || Tree[j][i+1]) T+=Dij.dij(j,i);//以j为源点的单源最短和，i是暂时删除的边
139             else T+=tot[j];
140         }
141         NC=max(NC,T);
142     }
143     printf("%d %d\n",C,NC);
144 }
145 int main()
146 {
147     while(cin>>N>>M>>L)
148     {
149         read();
150         init_c();
151         solve();
152     }
153 }