2017CCPC中南地區賽 H題

題目地址：202.197.224.59/OnlineJudge2/

來自湘潭大學OJ，題號：1267。

這裡用到了一個樹的直徑（樹中的最長邊）的結論：當你找到一棵樹的最長邊後，這個樹中所有點的最長邊必定和這條邊的兩個端點相連。下面給出證明：

設這條最長邊的兩個端點分別為B和E；

1.當選擇的任意點M在這條最長邊上時：如果此時還存在另一個點T，使得MT > max{MB,ME}。則：MT + min{MB,ME} > max{MB,ME} + min{MB,ME} = BE這與題目假設相矛盾。

2.當選擇的任意點M不在這條最長邊上時：

Α.與它相連的最長邊與BE有交點時，假設交於X，則：M的最長邊 = MX + X的最長邊，而X在BE上，所以M的最長邊 = MX + max{XB，XE}即它的最長邊終止於BE中的一個點。

B.若無交點，假設M的最長邊為MN，則：取BE上一點X，連接MX，有：MN > max{XB,XE} + XM，MN + MX + max{XB,XE} > 2MX + 2max{XB,XE} > BE與題設矛盾

由此，本題思路即為：先找到最長邊，然後將其餘的n - 2個點到最長邊兩個端點的距離算出，不斷地挑選這n-2個點到兩個端點的更長的那個路徑，最後加上這條最長路就是所求結果。

下面的代碼用C++11提交能過，而用G++則會WA

#include
#include
#include
#include
#include
#include
#define maxn 100005
#define F 0x3f
using namespace std;
struct edge
{
int len,over;
edge(int a = 0,int b = 0)
{
len = a,over = b;
}
};
long long dist[3][maxn];
vector graph[maxn];
inline void init
{
for(int i = 1;i < maxn;++i) graph[i].clear; } queue q;
void bfs(int use,int start)
{
while(q.size) q.pop;
q.push(start);
dist[use][start] = 0;
while(q.size){
int temp = q.front;
q.pop;
for(int i = 0;i < graph[temp].size;++i){ int length = graph[temp][i].len,nextone = graph[temp][i].over; if(dist[use][nextone] == -1){ dist[use][nextone] = dist[use][temp] + length; q.push(nextone); } } } return; } int main { int n; while(scanf("%d",&n) == 1){ int start,over,len; init; for(int i = 0;i < n - 1;++i){ scanf("%d%d%d",&start,&over,&len); graph[start].push_back(edge(len,over)); graph[over].push_back(edge(len,start)); } int point1,point2; memset(dist,-1,sizeof(dist)); //printf("now dist is %lld ",dist[0][0]); bfs(0,1); long long maxone = 0; for(int i = 2;i <= n;++i){ if(dist[0][i] > maxone) maxone = dist[0][i],point1 = i;
}
maxone = 0;
bfs(1,point1);
for(int i = 1;i <= n;++i){ if(dist[1][i] > maxone) maxone = dist[1][i],point2 = i;
}
bfs(2,point2);
//printf("point1 is %d and point2 is %d
",point1,point2);
long long answer = 0;
answer += dist[1][point2];
for(int i = 1;i <= n;++i){ if(i != point1 && i != point2){ answer += max(dist[1][i],dist[2][i]); } } if(n == 1) answer = 0; printf("%lld ",answer); } return 0; }

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！