LOJ10068秘密的牛奶运输
题目描述
Farmer John 要把他的牛奶运输到各个销售点。运输过程中，可以先把牛奶运输到一些销售点，再由这些销售点分别运输到其他销售点。 运输的总距离越小，运输的成本也就越低。低成本的运输是 Farmer John 所希望的。不过，他并不想让他的竞争对手知道他具体的运输方案，所以他希望采用费用第二小的运输方案而不是最小的。现在请你帮忙找到该运输方案。
输入格式
第一行是两个整数 N,M，表示顶点数和边数；
接下来 M 行每行 3 个整数，x,y,z，表示一条路的两端x,y 和距离z。
输出格式
仅一行，输出第二小方案。
样例
样例输入
4 4
1 2 100
2 4 200
2 3 250
3 4 100样例输出
450数据范围与提示
对于全部数据，1≤N≤500,1≤M≤10^4,1≤z≤10^9，数据可能有重边。
__________________________________________________________________
严格次小生成树。
ff[i][j]表示：i点向上跳2^j步经过的最大值
fs[i][j]表示：i点向上跳2^j步经过的次大值
这个样枚举每一条边，替换边的两点（u,v）之间在树上的链的最大值或次大值（如果边的权和最大值的权相等），求得的就可能是次小生成树。在所有可能的次小生成树中求最小的就是结果。
__________________________________________________________________
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=505; 4 const int maxm=1e4+10; 5 int n,m; 6 struct edge 7 { 8 int u,v,w,nxt; 9 }e[maxn<<1],ee[maxm]; 10 int head[maxn],js,jss; 11 long long ans=1000000000000000ll,tt; 12 void addage(int u,int v,int w) 13 { 14 e[++js].u=u;e[js].v=v;e[js].w=w; 15 e[js].nxt=head[u];head[u]=js; 16 } 17 void addagef(int u,int v,int w) 18 { 19 ee[jss].u=u;ee[jss].v=v;ee[jss++].w=w; 20 } 21 bool cmp(edge a,edge b) 22 { 23 return a.w<b.w; 24 } 25 int fa[maxn]; 26 int find(int x) 27 { 28 return fa[x]==x?x:fa[x]=find(fa[x]); 29 } 30 int f[maxn][10],ff[maxn][10],fs[maxn][10],dep[maxn]; 31 void dfs(int u,int fat) 32 { 33 dep[u]=dep[fat]+1; 34 for(int i=head[u];i;i=e[i].nxt) 35 { 36 int v=e[i].v; 37 if(v!=fat) 38 { 39 f[v][0]=u; 40 ff[v][0]=e[i].w; 41 for(int i=1;i<10;++i) 42 { 43 f[v][i]=f[f[v][i-1]][i-1]; 44 int a=ff[v][i-1],b=ff[f[v][i-1]][i-1],c=fs[v][i-1],d=fs[f[v][i-1]][i-1]; 45 ff[v][i]=max(a,b); 46 if(a==b)fs[v][i]=max(c,d); 47 else if(a>b)fs[v][i]=max(b,c); 48 else fs[v][i]=max(a,d); 49 } 50 dfs(v,u); 51 } 52 } 53 } 54 int lg[maxn]; 55 int lca(int u,int v) 56 { 57 lg[0]=-1; 58 for(int i=1;i<=n;++i)lg[i]=lg[i>>1]+1; 59 if(dep[u]<dep[v])swap(u,v); 60 while(dep[u]>dep[v])u=f[u][lg[dep[u]-dep[v]]]; 61 if(u==v)return u; 62 for(int i=lg[dep[u]];i>=0;--i) 63 if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i]; 64 return f[u][0]; 65 } 66 void work(int u,int l,int &mx,int &se) 67 { 68 while(dep[u]>dep[l]) 69 { 70 int a=ff[u][lg[dep[u]-dep[l]]],c=fs[u][lg[dep[u]-dep[l]]]; 71 u=f[u][lg[dep[u]-dep[l]]]; 72 int b=mx,d=se; 73 mx=max(a,b); 74 if(a==b)se=max(c,d); 75 else if(a>b)se=max(b,c); 76 else se=max(a,d); 77 } 78 } 79 int main() 80 { 81 scanf("%d%d",&n,&m); 82 for(int u,v,w,i=0;i<m;++i) 83 { 84 scanf("%d%d%d",&u,&v,&w); 85 addagef(u,v,w); 86 } 87 sort(ee,ee+m,cmp); 88 for(int i=1;i<=n;++i)fa[i]=i; 89 for(int i=0;i<m;++i) 90 { 91 int a=find(ee[i].u),b=find(ee[i].v); 92 if(a!=b) 93 { 94 fa[a]=b; 95 addage(ee[i].u,ee[i].v,ee[i].w); 96 addage(ee[i].v,ee[i].u,ee[i].w); 97 ee[i].nxt=1; 98 tt+=ee[i].w; 99 if(js==2*n-2)break; 100 } 101 } 102 dfs(1,0); 103 for(int u,v,w,l,i=0;i<m;++i) 104 if(ee[i].nxt==0) 105 { 106 u=ee[i].u;v=ee[i].v;w=ee[i].w; 107 l=lca(u,v); 108 int a=0,b=0,c=0,d=0,mx,se; 109 work(u,l,a,c); 110 work(v,l,b,d); 111 mx=max(a,b); 112 if(a==b)se=max(c,d); 113 else if(a>b)se=max(b,c); 114 else se=max(a,d); 115 if(mx!=w) ans=min(ans,tt+w-mx); 116 else if(w==mx && se!=0)ans=min(ans,tt+w-se); 117 } 118 cout<<ans; 119 return 0; 120 }
View Code