|
关于次小生成树 TreeLCA的位运算我们有实例! 小 C 最近学了很多最小生成树的算法Prim 算法Kurskal 算法消圈算法 等等 正当小 C 洋洋得意之时小 P 又来泼小 C 冷水了小 P 说让小 C 求出一 个无向图的次小生成树而且这个次小生成树还得是严格次小的也就是说 如果最小生成树选择的边集是 EM严格次小生成树选择的边集是 ES那么 需要满足(value(e) 表示边 e的权值) 这下小 C 蒙了他找到了你希望你帮他解决这个问题 Input 第一行包含两个整数N 和M表示无向图的点数与边数 接下来 M行每行 个数x y z 表示点 x 和点y之间有一条边边的权值 为z Output 包含一行仅一个数表示严格次小生成树的边权和(数 据保证必定存在严格次小生成树) Sample Input Sample Output
HINT 数据中无向图无自环; % 的数据N≤ M≤ ; % 的数据N≤ M≤ ; % 的数据N≤ M≤ 边权值非负且不超过 ^
Source 这题的关键就在于求Lca记录路径上的最小与严格次小值 用f[i][j]表示i的第^j个儿子( 表示 不存在) 那么f[i][j]=f[ f[i][ j] ][j] dp[i][j]和dp[i][j]表示点i到f[i][j]的最小和严格次小值(不存在=)那么只需特判即可 [cpp] int lca(int xint yint &nowdpint &nowdp) { if (deep[x]<deep[y]) swap(xy); int t=deep[x]deep[y]; //差的数量 for (int i=;t;i++) if (t&bin[i]) //转化为位运算 bin[i]表示<<i 把t看成进制 { x=f[x][i]; t=bin[i]; } int i=Li; //Li 表示 最高存到^(Li)个父亲 while (x^y) //x和y不相等时 { while (f[x][i]==f[y][i]&&i) i; //当i==时只能向上跳 x=f[x][i];y=f[y][i]; } } 程序 [cpp] #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<functional> using namespace std; #define MAXN (+) #define MAXM (+) #define Li () #define INF () int edge[MAXM]pre[MAXM]weight[MAXM]next[MAXM]size=; int addedge(int uint vint w) { edge[++size]=v; weight[size]=w; next[size]=pre[u]; pre[u]=size; } int addedge(int uint vint w) { addedge(uvw); addedge(vuw); } int f[MAXN][Li]={}dp[MAXN][Li]={}dp[MAXN][Li]={}deep[MAXN]nm; struct E { int uvw; friend bool operator<(E aE b){return aw<bw; } }e[MAXM]; bool b[MAXM]vis[MAXN]; int queue[MAXN]headtail; void bfs() { memset(vissizeof(vis)); head=tail=;queue[]=;vis[]=;deep[]=; while (head<=tail) { int &u=queue[head]; if (u!=) { for (int i=;i<;i++) { if (f[u][i]) { f[u][i]=f[f[u][i]][i]; } if (f[u][i]==) break; if (f[u][i]) { dp[u][i]=max(dp[u][i]dp[f[u][i]][i]); } if (i==) { if (dp[u][]!=dp[f[u][]][]) dp[u][]=min(dp[u][]dp[f[u][]][]); else dp[u][]=; } else { dp[u][i]=max(dp[u][i]dp[f[u][i]][i]); if (dp[u][i]!=dp[f[u][i]][i]) dp[u][i]=max(dp[u][i]min(dp[u][i]dp[f[u][i]][i])); } } } for (int p=pre[u];p;p=next[p]) { int &v=edge[p]; if (!vis[v]) { queue[++tail]=v; vis[v]=;deep[v]=deep[u]+; f[v][]=u;dp[v][]=weight[p];dp[v][]=; } } head++; } } int bin[Li]; void check(int &nowdpint &nowdpint c) { if (c<=nowdp) return; else if (nowdp<c&&c<nowdp) nowdp=c; else if (c==nowdp) return; else if (nowdp<c) {nowdp=nowdp;nowdp=c;} } int lca(int xint yint &nowdpint &nowdp) { nowdp=nowdp=; if (deep[x]<deep[y]) swap(xy); int t=deep[x]deep[y]; for (int i=;t;i++) if (t&bin[i]) { check(nowdpnowdpdp[x][i]); check(nowdpnowdpdp[x][i]); x=f[x][i]; t=bin[i]; } int i=Li; while (x^y) { while (f[x][i]==f[y][i]&&i) i; check(nowdpnowdpdp[x][i]); check(nowdpnowdpdp[x][i]); check(nowdpnowdpdp[y][i]); check(nowdpnowdpdp[y][i]); x=f[x][i];y=f[y][i]; } } int father[MAXN]; long long sum_edge=; int getfather(int x) { if (father[x]==x) return x; father[x]=getfather(father[x]); return father[x]; } void union(int xint y) { father[father[x]]=father[father[y]]; } int main() { scanf(%d%d&n&m); for (int i=;i<=n;i++) father[i]=i; memset(bsizeof(b)); memset(nextsizeof(next)); for (int i=;i<Li;i++) bin[i]=<<i; for (int i=;i<=m;i++) { scanf(%d%d%d&e[i]u&e[i]v&e[i]w); } sort(e+e++m); for (int i=;i<=m;i++) { if (getfather(e[i]u)!=getfather(e[i]v)) {union(e[i]ue[i]v);addedge(e[i]ue[i]ve[i]w);sum_edge+=e[i]w; } else b[i]=; } bfs(); long long mindec=; for (int i=;i<=m;i++) if (b[i]) { int nowdpnowdp; lca(e[i]ue[i]vnowdpnowdp); if (nowdp==e[i]w) nowdp=nowdp; if (nowdp==) continue; if (mindec==||mindec>e[i]wnowdp) mindec=e[i]wnowdp; } printf(%lld\nsum_edge+mindec); return ; } |
