2015
02-21

There is a magic planet in the space. There is a magical country on the planet. There are N cities in the country. The country is magical because there are exactly N-1 magic roads between the N cities, and from each city, it is possible to visit any other city. But after the huge expansion of the country, the road system seems to be messy. The moderator decided to rebuild the road system.

As a worker, I cannot do too much things. I could just move one road to another position connecting arbitrary 2 cities using my magic, keeping its length unchanged. Of course, afterwards all the N cities have to be still connected. I wonder how to move in order to make the farthest distance between any two cities minimum. Could you solve it for me?

The first line of the input is one integer T (T ≤ 10), and then T test cases follow.
Each test case begins with a line contains only one integer N (N ≤ 2500), means there are N magic cities. The cities are numbered from 0 to N-1.
Following N-1 lines, each line has 3 integers a, b and c, means there is a magic road between a and b with distance c. (0 <= a, b < N, 0 < c <= 1000)

The first line of the input is one integer T (T ≤ 10), and then T test cases follow.
Each test case begins with a line contains only one integer N (N ≤ 2500), means there are N magic cities. The cities are numbered from 0 to N-1.
Following N-1 lines, each line has 3 integers a, b and c, means there is a magic road between a and b with distance c. (0 <= a, b < N, 0 < c <= 1000)

2
4
0 1 2
1 2 2
2 3 2
5
0 1 1
1 2 2
2 3 3
3 4 4

Case 1: 4
Case 2: 7

 #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

const int maxn=2555;
const int oo=0x3fffffff;
int visit[maxn], pre[10*maxn];
int stack[10*maxn], sa[10*maxn], sb[10*maxn];
int color[10*maxn];
int st, sd, ans, edge;

struct Node
{
int u, e;
int dis;
};
queue<Node>q;

inline void addedge(int u, int v, int c)
{
}

void bfs(int ss,int op)
{
memset(visit,0,sizeof(visit));
while(!q.empty()) q.pop();
Node s, p;
s.u=ss, s.dis=0, s.e=-1, sd=-1, st=ss;
q.push(s);
visit[ss]=1;
int maxx=0, pos;
while(!q.empty())
{
p=q.front();
q.pop();
{
if(color[i]||color[i^1]) continue;
int v=reach[i], val=flow[i];
s.u=v, s.dis=p.dis+val, s.e=i;
if(!visit[s.u])
{
visit[s.u]=1;
pre[s.e]=p.e;
if(s.dis>maxx)
{
st=s.u;
maxx=s.dis;
sd=s.e;
}
q.push(s);
}
}
}
++op;
if(op==1) bfs(st,op);
else  ans=maxx;
}

int cal(int s[], int n, double len)  ///找最靠近中点的点
{
int sum=0;
for(int i=0; i<n; i++)
{
sum+=flow[s[i]];
if(sum>=len)
{
if(sum-len<=len-(sum-flow[ s[i] ])) return reach[ s[i]^1 ];
else return reach[ s[i] ];
}
}
}

int Solve(int n)
{
int MIN=oo;
memset(color,0,sizeof(color));
memset(pre,-1,sizeof(pre));
bfs(1,0);
int top=0;
while(sd!=-1) stack[top++]=sd,sd=pre[sd];
for(int i=0; i<top; i++)  ///枚举最长路上的所有边
{
int x=stack[i], na=0, nb=0;
color[x]=1;
for(int j=0; j<edge; j++) pre[j]=-1;
bfs(reach[x],0);
while(sd!=-1) sa[na++]=sd, sd=pre[sd];
int u=cal(sa,na,1.0*ans/2);
if(!na) u=reach[x];
for(int j=0; j<edge; j++) pre[j]=-1;
bfs(reach[x^1],0);
while(sd!=-1) sb[nb++]=sd,  sd=pre[sd];
int v=cal(sb,nb,1.0*ans/2);
if(!nb) v=reach[x^1];
bfs(1,0);
MIN=min(MIN,ans);
color[edge-1]=1;    ///注意把新加的边移除，
color[x]=0;
}
return MIN;
}

int main()
{
int n, T, tcase=0;
cin >> T;
while(T--)
{
cin >> n;
edge=0;
for(int i=1; i<n; i++)
{
int a, b, c;
scanf("%d%d%d",&a,&b,&c);
}
int tmp=Solve(n);
printf("Case %d: %d\n",++tcase,tmp);
}
}
/*
10
9
0 1 1
1 2 1
2 3 1
2 4 1
0 5 1
5 6 1
5 7 1
7 8 1
4
0 1 2
1 2 2
2 3 2
5
0 1 1
1 2 2
2 3 3
3 4 4
*/


, ,
1. 世界灵异事件之一，漫步的孩子。晚上1***点1***分，楼房角落可以看见一个原地踏步走的孩子，看不见他的脸，如果没将这消息传五个帖子，将家破人亡，被那个***于非命的孩子夺取心脏。对不起了，我也是无意中看到的，我不想失去家人，所以只能发了。抱歉世界灵异事

2. 世界灵异事件之一，漫步的孩子。晚上1***点1***分，楼房角落可以看见一个原地踏步走的孩子，看不见他的脸，如果没将这消息传五个帖子，将家破人亡，被那个***于非命的孩子夺取心脏。对不起了，我也是无意中看到的，我不想失去家人，所以只能发了。抱歉世界灵异事

3. 世界灵异事件之一，漫步的孩子。晚上1***点1***分，楼房角落可以看见一个原地踏步走的孩子，看不见他的脸，如果没将这消息传五个帖子，将家破人亡，被那个***于非命的孩子夺取心脏。对不起了，我也是无意中看到的，我不想失去家人，所以只能发了。抱歉世界灵异事

4. 世界灵异事件之一，漫步的孩子。晚上1***点1***分，楼房角落可以看见一个原地踏步走的孩子，看不见他的脸，如果没将这消息传五个帖子，将家破人亡，被那个***于非命的孩子夺取心脏。对不起了，我也是无意中看到的，我不想失去家人，所以只能发了。抱歉世界灵异事

5. 世界灵异事件之一，漫步的孩子。晚上1***点1***分，楼房角落可以看见一个原地踏步走的孩子，看不见他的脸，如果没将这消息传五个帖子，将家破人亡，被那个***于非命的孩子夺取心脏。对不起了，我也是无意中看到的，我不想失去家人，所以只能发了。抱歉世界灵异事

6. 世界灵异事件之一，漫步的孩子。晚上1***点1***分，楼房角落可以看见一个原地踏步走的孩子，看不见他的脸，如果没将这消息传五个帖子，将家破人亡，被那个***于非命的孩子夺取心脏。对不起了，我也是无意中看到的，我不想失去家人，所以只能发了。抱歉世界灵异事

7. 世界灵异事件之一，漫步的孩子。晚上1***点1***分，楼房角落可以看见一个原地踏步走的孩子，看不见他的脸，如果没将这消息传五个帖子，将家破人亡，被那个***于非命的孩子夺取心脏。对不起了，我也是无意中看到的，我不想失去家人，所以只能发了。抱歉世界灵异事

8. 世界灵异事件之一，漫步的孩子。晚上1***点1***分，楼房角落可以看见一个原地踏步走的孩子，看不见他的脸，如果没将这消息传五个帖子，将家破人亡，被那个***于非命的孩子夺取心脏。对不起了，我也是无意中看到的，我不想失去家人，所以只能发了。抱歉世界灵异事

9. 世界灵异事件之一，漫步的孩子。晚上1***点1***分，楼房角落可以看见一个原地踏步走的孩子，看不见他的脸，如果没将这消息传五个帖子，将家破人亡，被那个***于非命的孩子夺取心脏。对不起了，我也是无意中看到的，我不想失去家人，所以只能发了。抱歉世界灵异事

10. 世界灵异事件之一，漫步的孩子。晚上1***点1***分，楼房角落可以看见一个原地踏步走的孩子，看不见他的脸，如果没将这消息传五个帖子，将家破人亡，被那个***于非命的孩子夺取心脏。对不起了，我也是无意中看到的，我不想失去家人，所以只能发了。抱歉世界灵异事

11. 世界灵异事件之一，漫步的孩子。晚上1***点1***分，楼房角落可以看见一个原地踏步走的孩子，看不见他的脸，如果没将这消息传五个帖子，将家破人亡，被那个***于非命的孩子夺取心脏。对不起了，我也是无意中看到的，我不想失去家人，所以只能发了。抱歉世界灵异事

12. 世界灵异事件之一，漫步的孩子。晚上1***点1***分，楼房角落可以看见一个原地踏步走的孩子，看不见他的脸，如果没将这消息传五个帖子，将家破人亡，被那个***于非命的孩子夺取心脏。对不起了，我也是无意中看到的，我不想失去家人，所以只能发了。抱歉世界灵异事

13. 世界灵异事件之一，漫步的孩子。晚上1***点1***分，楼房角落可以看见一个原地踏步走的孩子，看不见他的脸，如果没将这消息传五个帖子，将家破人亡，被那个***于非命的孩子夺取心脏。对不起了，我也是无意中看到的，我不想失去家人，所以只能发了。抱歉世界灵异事

14. 世界灵异事件之一，漫步的孩子。晚上1***点1***分，楼房角落可以看见一个原地踏步走的孩子，看不见他的脸，如果没将这消息传五个帖子，将家破人亡，被那个***于非命的孩子夺取心脏。对不起了，我也是无意中看到的，我不想失去家人，所以只能发了。抱歉世界灵异事

15. 世界灵异事件之一，漫步的孩子。晚上1***点1***分，楼房角落可以看见一个原地踏步走的孩子，看不见他的脸，如果没将这消息传五个帖子，将家破人亡，被那个***于非命的孩子夺取心脏。对不起了，我也是无意中看到的，我不想失去家人，所以只能发了。抱歉世界灵异事

16. 世界灵异事件之一，漫步的孩子。晚上1***点1***分，楼房角落可以看见一个原地踏步走的孩子，看不见他的脸，如果没将这消息传五个帖子，将家破人亡，被那个***于非命的孩子夺取心脏。对不起了，我也是无意中看到的，我不想失去家人，所以只能发了。抱歉世界灵异事

17. 世界灵异事件之一，漫步的孩子。晚上1***点1***分，楼房角落可以看见一个原地踏步走的孩子，看不见他的脸，如果没将这消息传五个帖子，将家破人亡，被那个***于非命的孩子夺取心脏。对不起了，我也是无意中看到的，我不想失去家人，所以只能发了。抱歉世界灵异事

18. 世界灵异事件之一，漫步的孩子。晚上1***点1***分，楼房角落可以看见一个原地踏步走的孩子，看不见他的脸，如果没将这消息传五个帖子，将家破人亡，被那个***于非命的孩子夺取心脏。对不起了，我也是无意中看到的，我不想失去家人，所以只能发了。抱歉世界灵异事

19. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

20. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

21. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。

22. #include <stdio.h>
int main()
{
int n,p,t[100]={1};
for(int i=1;i<100;i++)
t =i;
while(scanf("%d",&n)&&n!=0){
if(n==1)
printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
else {
if(n%4) p=n/4+1;
else p=n/4;
int q=4*p;
printf("Printing order for %d pages:n",n);
for(int i=0;i<p;i++){
printf("Sheet %d, front: ",i+1);
if(q>n) {printf("Blank, %dn",t[2*i+1]);}
else {printf("%d, %dn",q,t[2*i+1]);}
q–;//打印表前
printf("Sheet %d, back : ",i+1);
if(q>n) {printf("%d, Blankn",t[2*i+2]);}
else {printf("%d, %dn",t[2*i+2],q);}
q–;//打印表后
}
}
}
return 0;
}

23. 代码是给出了，但是解析的也太不清晰了吧！如 13 abejkcfghid jkebfghicda
第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3)，为什么要这样拆分，原则是什么？