codevs 1700 施工方案第二季

c国边防军在边境某处的阵地是由n个地堡组成的。工兵连受命来到阵地要进行两期施工。

第一期的任务是挖掘暗道让所有地堡互联互通。现已勘测设计了m条互不相交的暗道挖掘方案，如果这m条暗道都实施挖掘，肯定能达到互联互通的目的。事实上，适当选择其中n-1个方案挖掘，就能实现互联互通，即从每个地堡出发都能到达其他任何一个地堡（允许经过别的地堡）。

连长精心谋算，在m个设计规划中选取了挖掘总距离最短且能保证互联互通的若干个暗道规划实施了挖掘，完成了第一期的施工任务后又接受了第二期的施工任务，要求选择一个地堡进行扩建改造，使其能向每个地堡提供弹药。为了让弹药供应更及时、更快捷，从改扩建的地堡到最远地堡的距离（称为最远输送距离）应当尽量小。

你的任务是先求出第一期施工挖掘的总距离，再求改扩建地堡最远输送距离的最小值。

其中第一行是n和m，m>=n
下面的m行每行3个数xi、yi、zi,表示xi到yi的距离是zi
  zi<1000000且m个距离互不相等

共包含两行，每行一个整数，
第一行是第一期的挖掘总距离，第二行是最远输送距离的最小值。

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

6
3

【样例说明】
第一期挖掘1到2、2到3和3到4的3条暗道，第二期选择3号地堡进行改扩建，最远输送距离是3
【数据规模】
60%的数据 n<10且m<20
80%的数据 n<1000且m<2000
100%的数据 n<100000且m<200000

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXNCNT 100010
#define MAXEDGE 200010
using namespace std;
long long ans,ans2;
int n,m,tot,src,decc,home;
long long minn=0x7f7f7f7f,mann=0x7f7f7f7f;
long long dis[MAXNCNT],cap[MAXEDGE*];
long long sum1[MAXNCNT],sum2[MAXNCNT];
int fa[MAXNCNT],dad[MAXNCNT],vis[MAXNCNT];
int to[MAXEDGE*],net[MAXEDGE*],head[MAXNCNT];
struct nond{ int u,v;long long w; }v[MAXEDGE];
int abs(int x){ return x>?x:-x; }
int cmp(nond a,nond b){ return a.w<b.w; }
int find(int x){ return fa[x]==x?x:fa[x]=find(fa[x]); }
void add(int u,int v,long long w){
to[++tot]=v;cap[tot]=w;net[tot]=head[u];head[u]=tot;
to[++tot]=u;cap[tot]=w;net[tot]=head[v];head[v]=tot;
}
void spfa(int s){
queue<int>que;
memset(vis,,sizeof(vis));
memset(dis,0x7f,sizeof(dis));
dis[s]=;vis[s]=;que.push(s);
while(!que.empty()){
int now=que.front();
que.pop();vis[now]=;
for(int i=head[now];i;i=net[i])
if(dis[to[i]]>dis[now]+cap[i]){
dis[to[i]]=dis[now]+cap[i];
if(!vis[to[i]]){
vis[to[i]]=;
que.push(to[i]);
}
}
}
}
void dfs(int now){
for(int i=head[now];i;i=net[i])
if(dis[to[i]]==-){
dis[to[i]]=dis[now]+cap[i];
dfs(to[i]);
}
}
void dfs1(int now){
for(int i=head[now];i;i=net[i])
if(dad[now]!=to[i]){
dad[to[i]]=now;
sum1[to[i]]=sum1[now]+cap[i];
dfs1(to[i]);
}
}
void dfs2(int now){
for(int i=head[now];i;i=net[i])
if(dad[now]!=to[i]){
dad[to[i]]=now;
sum2[to[i]]=sum2[now]+cap[i];
dfs2(to[i]);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
scanf("%d%d%lld",&v[i].u,&v[i].v,&v[i].w);
sort(v+,v++m,cmp);
for(int i=;i<=n;i++) fa[i]=i;
for(int i=;i<=m;i++){
int dx=find(v[i].u);
int dy=find(v[i].v);
if(dx==dy) continue;
fa[dy]=dx;ans+=v[i].w;
add(v[i].u,v[i].v,v[i].w);
}
printf("%lld\n",ans);
memset(dis,-,sizeof(dis));
decc=;dis[decc]=;dfs(decc);
for(int i=;i<=n;i++)
if(dis[i]>dis[decc]) decc=i;
memset(dis,-,sizeof(dis));
dis[decc]=;dfs(decc);src=decc;
for(int i=;i<=n;i++)
if(dis[i]>dis[decc]) decc=i;
dfs1(src);memset(dad,,sizeof(dad));
dfs2(decc);memset(dad,,sizeof(dad));
for(int i=;i<=n;i++){
long long little=abs(sum1[i]-sum2[i]);
if(little<minn){ mann=sum1[i];home=i;minn=little; }
else if(little==minn)
if(sum1[i]<mann){ mann=sum1[i];home=i; }
}
spfa(home);
for(int i=;i<=n;i++)
if(i!=home&&dis[i]>ans2) ans2=dis[i];
cout<<ans2;
}