testA
输入文件:
testA.in 输出文件testA.out
时限5000ms
问题描述：
一棵树N个节点,每条边有一个距W,现在定义SUM为所有dist(X,Y)的和1<=X<Y<=N
,
dist(X,Y)表示X到Y在树上的距离。现在给你一个机会把任意一条边删掉，再把这条边连接其他两个节点使得SUM最小。求出SUM的最小值
输入描述：
第一行N。
第二行到第N行每行三个数X,Y,W。表示X到Y有一条长度为W的边。
。
输出描述：
一行一个数表示答案。
数据范围N<=5000 , W<=10^6
样例输入1：
6
1
2 1
2 3 1
3 4 1
4 5 1
5 6 1
样例输出1：
29
样例输入2：
3
1
2 2
1 3 4
样例输出2：
12
就因为这道题卡了我很久啊。总之就是维护一堆乱七八糟的值。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 10000
#define MAXE MAXN*2
#define MAXV MAXN
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
typedef long long qword;
int n,m;
struct edge
{
int x,y;
}el[MAXE];
struct Edge
{
int np,val;
int id;
Edge *next;
}E[MAXE],*V[MAXV];
int root,tope=-;
void addedge(int x,int y,int z,int id)
{
E[++tope].np=y;
E[tope].next=V[x];
E[tope].val=z;
E[tope].id=id;
V[x]=&E[tope];
}
int fa[MAXN];
int dis_fa[MAXN];
int q[MAXN];
int ope=-,clo=;
int dp1[MAXN];//size of subtree
qword dp2[MAXN];//the total distance from each child to the root in subtree
qword dp3[MAXN];//the total distance from each node outside the subtree to root
qword dp4[MAXN];//the total distance of each pair
void bfs(int root)
{
ope=-,clo=;
Edge *ne;
q[]=root;
fa[root]=;
int now;
while (ope<clo)
{
now=q[++ope];
for (ne=V[now];ne;ne=ne->next)
{
if (ne->np==fa[now])continue;
fa[ne->np]=now;
dis_fa[ne->np]=ne->val;
q[++clo]=ne->np;
}
}
}
qword work1()
{
int i,j;
Edge *ne;
int now;
for (i=clo;i>=;i--)
{
now=q[i];
dp1[now]=;
for (ne=V[now];ne;ne=ne->next)
{
if (ne->np==fa[now])continue;
dp1[now]+=dp1[ne->np];
}
}
for (i=clo;i>=;i--)
{
now=q[i];
dp2[now]=;
for (ne=V[now];ne;ne=ne->next)
{
if (ne->np==fa[now])continue;
dp2[now]+=dp2[ne->np]+dp1[ne->np]*ne->val;
}
}
dp3[q[]]=;
for (i=;i<=clo;i++)
{
now=q[i];
// dp3[now]=dp3[fa[now]]+dp2[fa[now]]-dp2[now]+dis_fa[now]*(-dp1[now]+dp1[fa[now]]-dp1[now]);
dp3[now]=dp3[fa[now]]+dp2[fa[now]]-dp2[now]-dis_fa[now]*dp1[now]+dis_fa[now]*(dp1[root]-dp1[now]);
}
qword ret=;
for (i=;i<=n;i++)
{
ret+=(qword)dis_fa[i]*dp1[i]*(dp1[root]-dp1[i]);
}
return ret;
}
bool edge_st[MAXN];
int color[MAXN];
qword dist[MAXN];
void dfs2(int now,int fat,int col,qword d)
{
color[now]=col;
dist[now]=d;
Edge *ne;
for (ne=V[now];ne;ne=ne->next)
{
if (ne->np==fat)continue;
dfs2(ne->np,now,col,d+ne->val);
}
}
int main()
{
freopen("testA.in","r",stdin);
//freopen("testA.out","w",stdout);
int i,j,k;
int x,y,z;
scanf("%d",&n);
for (i=;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
addedge(x,y,z,i-);
addedge(y,x,z,i-);
el[i-].x=x;
el[i-].y=y;
}
m=n-;
root=;
bfs(root);
qword sum_old=work1();
//cout<<"SUM_OLD:"<<sum_old<<endl;
qword dis1,dis2;
qword dis_old1,dis_old2;
qword mus1,mus2;
int totm1,totm2;
qword best=;
for (i=;i<m;i++)
{
edge_st[i]=;
if (fa[el[i].x]==el[i].y)swap(el[i].x,el[i].y);
dfs2(el[i].x,el[i].y,,);//1:outside
dfs2(el[i].y,el[i].x,,);//2:inside
dis_old1=dp3[el[i].y]-dis_fa[el[i].y]*(dp1[root]-dp1[el[i].y]);
dis_old2=dp2[el[i].y];
mus1=dp2[el[i].y]+dp1[el[i].y]*dis_fa[el[i].y];
mus2=dp3[el[i].y];
totm1=dp1[el[i].y];
totm2=dp1[root]-dp1[el[i].y];
dis1=dis2=INF;
for (j=;j<=n;j++)
{
if (color[j]==)
{
dis2=min(dis2,dp2[j]+dp3[j]-mus2-totm2*dist[j]);
}else
{
dis1=min(dis1,dp2[j]+dp3[j]-mus1-totm1*dist[j]);
}
}
best=max(best,(dis_old1-dis1)*totm1+(dis_old2-dis2)*totm2);
}
printf(LL "\n",sum_old-best);
return ;
}