Description
　　給出N個(gè)點(diǎn),N-1條邊的連通圖.
　　現(xiàn)要求刪除一條邊,使得連通塊的直徑總和最大.所謂連通塊的直徑是指連通塊中最遠(yuǎn)兩點(diǎn)之間的距離。
　　 　　問(wèn):直徑總和最大是多少?

Input
　　文件名為 delete.in
　　第一行正整數(shù)N.
　　接下來(lái)N-1行.每行兩個(gè)數(shù),A,B,LEN表示A,B(1<=A,B<=N)有一條長(zhǎng)度為L(zhǎng)en(1<=Len<=1000)的邊連接著.

Output
　　文件名為 delete.out
　　一個(gè)數(shù)Ans.直徑總和的最大值.

Sample Input
10
2 1 982
3 1 169
4 1 934
5 1 325
6 1 735
7 1 675
8 2 302
9 3 450
10 5 173

Sample Output
2668

Data Constraint

Hint
【數(shù)據(jù)范圍】
　　30% N<=100
　　70% N<=5000
　　100% N<=100000
.
.
.
.
.
.

分析

我們要預(yù)處理出每一棵子樹(shù)的直徑和子樹(shù)中的最遠(yuǎn)點(diǎn)，次遠(yuǎn)點(diǎn)和子樹(shù)中過(guò)x的最長(zhǎng)鏈、次長(zhǎng)鏈和次次長(zhǎng)鏈
那么考慮刪去一條邊后直徑有哪幾種情況
①在x的子樹(shù)里
②在x上面的聯(lián)通塊的直徑
③x子樹(shù)沒(méi)被刪去的最遠(yuǎn)點(diǎn)與x上方最遠(yuǎn)點(diǎn)的和
④在x不同子樹(shù)上最遠(yuǎn)的點(diǎn)的和

考慮一下怎么求：
①預(yù)處理得出
②在遞歸時(shí)可以記錄當(dāng)前經(jīng)過(guò)聯(lián)通塊的最大值
③x子樹(shù)里的在預(yù)處理里已經(jīng)求出來(lái)，那么不在x子樹(shù)里的也就是遞歸經(jīng)過(guò)x的最長(zhǎng)鏈
④也就是在x子樹(shù)里不含被刪子樹(shù)的最遠(yuǎn)點(diǎn)和次遠(yuǎn)點(diǎn)
.
.
.
.
.

程序：

#include<iostream> using namespace std; int m[2][100001][4],d[2][100001][4],fa[100001],head[100001],dis[100001],ans,n,cnt;struct edge { int to,from,v; }rp[200001];void insert(int x,int y,int z) { rp[++cnt].to=y;rp[cnt].v=z;rp[cnt].from=head[x];head[x]=cnt; }void dfs(int x) {for (int i=head[x];i;i=rp[i].from){int w=rp[i].to;if (w!=fa[x]){fa[w]=x;dfs(w);dis[x]=max(dis[x],dis[w]);if (dis[w]>m[0][x][1]){m[0][x][2]=m[0][x][1];m[0][x][1]=dis[w];d[0][x][1]=w;} else if (dis[w]>m[0][x][2]) m[0][x][2]=dis[w];int v=m[1][w][1]+rp[i].v;if (v>m[1][x][1]){m[1][x][3]=m[1][x][2];m[1][x][2]=m[1][x][1];m[1][x][1]=v;d[1][x][2]=d[1][x][1];d[1][x][1]=w;} elseif (v>m[1][x][2]){m[1][x][3]=m[1][x][2];m[1][x][2]=v;d[1][x][2]=w;} else if (v>m[1][x][3]) m[1][x][3]=v;}}dis[x]=max(m[1][x][1]+m[1][x][2],m[0][x][1]); }void find(int x,int a,int b) {int m1,m2,m3;if (x!=1) ans=max(ans,dis[x]+a);for (int i=head[x];i;i=rp[i].from){int v=rp[i].to;if (v!=fa[x]){if (d[1][x][1]==v){m1=m[1][x][2];m2=m[1][x][2]+m[1][x][3];} else{m1=m[1][x][1];if (d[1][x][2]==v) m2=m[1][x][1]+m[1][x][3]; else m2=m[1][x][1]+m[1][x][2];}if (d[0][x][1]==v) m3=m[0][x][2]; else m3=m[0][x][1];find(v,max(max(a,m3),max(m1+b,m2)),max(b,m1)+rp[i].v);}} } int main() {cin>>n;for (int i=1;i<=n-1;i++){int x,y,z;cin>>x>>y>>z;insert(x,y,z); insert(y,x,z);}dfs(1);find(1,0,0);cout<<ans;return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9499936.html

總結(jié)

以上是生活随笔為你收集整理的删边的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。