「BZOJ1977」[BJ2010组队] 次小生成树 Tree
Description
小 C 最近学了很多最小生成树的算法，Prim 算法、Kurskal 算法、消圈算法等等。 正当小 C 洋洋得意之时，小 P 又来泼小 C 冷水了。小 P 说，让小 C 求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说： 如果最小生成树选择的边集是 EM，严格次小生成树选择的边集是 ES，那么需要满足：(value(e) 表示边 e的权值) 
这下小 C 蒙了，他找到了你，希望你帮他解决这个问题。
Input
第一行包含两个整数N 和M，表示无向图的点数与边数。 接下来 M行，每行 3个数x y z 表示，点 x 和点y之间有一条边，边的权值为z。
Output
包含一行，仅一个数，表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)
Sample Input
5 6
1 2 1
1 3 2
2 4 3
3 5 4
3 4 3
4 5 6
1 2 1
1 3 2
2 4 3
3 5 4
3 4 3
4 5 6
Sample Output
11
HINT
数据中无向图无自环； 50% 的数据N≤2 000 M≤3 000； 80% 的数据N≤50 000 M≤100 000； 100% 的数据N≤100 000 M≤300 000 ，边权值非负且不超过 10^9 。
题解
先求出最小生成树
要严格次小。。。
枚举每一条非树边找俩顶点树链上的最大边（如果最大边相同与非树边边权相同则找次大边）然后更新最小增量
最大边和次大边可以通过树上倍增求出
复杂度似乎是最小生成树mlogm，枚举边乱搞mlogn，所以是mlog(mn)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 |
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #define N 100001 #define M 300001 #define inf 0x7fffffff #define ll long long using namespace std; int n,m,tot,cnt,mn=inf; ll ans; int f[N],head[N],deep[N],fa[N][17],d1[N][17],d2[N][17]; struct data{int x,y,v;bool sel;}a[M]; struct edge{int to,next,v;}e[N*2]; bool cmp(data a,data b) {return a.v<b.v;} void ins(int u,int v,int w) {e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;} void insert(int u,int v,int w) {ins(u,v,w);ins(v,u,w);} int find(int x){return x==f[x]?x:find(f[x]);} void dfs(int x,int f) { for(int i=1;i<=16;i++) { if(deep[x]<(1<<i))break; fa[x][i]=fa[fa[x][i-1]][i-1]; d1[x][i]=max(d1[x][i-1],d1[fa[x][i-1]][i-1]); if(d1[x][i-1]==d1[fa[x][i-1]][i-1]) d2[x][i]=max(d2[x][i-1],d2[fa[x][i-1]][i-1]); else { d2[x][i]=min(d1[x][i-1],d1[fa[x][i-1]][i-1]); d2[x][i]=max(d2[x][i-1],d2[x][i]); d2[x][i]=max(d2[x][i],d2[fa[x][i-1]][i-1]); } } for(int i=head[x];i;i=e[i].next) if(e[i].to!=f) { fa[e[i].to][0]=x; d1[e[i].to][0]=e[i].v; deep[e[i].to]=deep[x]+1; dfs(e[i].to,x); } } int lca(int x,int y) { if(deep[x]<deep[y])swap(x,y); int t=deep[x]-deep[y]; for(int i=0;i<=16;i++) if((1<<i)&t)x=fa[x][i]; for(int i=16;i>=0;i--) { if(fa[x][i]!=fa[y][i]) {x=fa[x][i];y=fa[y][i];} } if(x==y)return x; return fa[x][0]; } void cal(int x,int f,int v) { int mx1=0,mx2=0; int t=deep[x]-deep[f]; for(int i=0;i<=16;i++) { if(t&(1<<i)) { if(d1[x][i]>mx1) { mx2=mx1; mx1=d1[x][i]; } mx2=max(mx2,d2[x][i]); x=fa[x][i]; } } if(mx1!=v)mn=min(mn,v-mx1); else mn=min(mn,v-mx2); } void solve(int t,int v) { int x=a[t].x,y=a[t].y,f=lca(x,y); cal(x,f,v);cal(y,f,v); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v); sort(a+1,a+m+1,cmp); for(int i=1;i<=m;i++) { int p=find(a[i].x),q=find(a[i].y); if(p!=q) { f[p]=q; ans+=a[i].v; a[i].sel=1; insert(a[i].x,a[i].y,a[i].v); tot++;if(tot==n-1)break; } } dfs(1,0); for(int i=1;i<=m;i++) if(!a[i].sel)solve(i,a[i].v); printf("%lld",ans+mn); return 0; } |
计数器 9854590
OI 课件=>
OI 课件=>
据说Tarjan_LCA更快更好写