[The 2011 ACM-ICPC Asia Chengdu Regional Contest]H.Holiday's Accommodation

2011年成都赛区H题的题解。

对于每一条边,设它左边有X个点,右边有Y个点,则显然有min(X,Y)*2个点会经过这条边,所以答案=sum{每条边的长度乘以会经过这条边的点数}。然后需要动态规划一下。据现场经验,不能直接DFS来动规(会爆栈),需要BFS。
然后,我现在正在学习Java所以代码是用Java写的,呵呵。这是我用Java写的第一个AC的程序哦。
CODE:
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2011-11-11
DESCRIPTION:
$DESCRIPTION
*/


import
java.io.*;
import
java.util.*;

public class
Main {
public static
void main(String args[])
{

new
Main();
}

public class
Graph {
public class
edge {
public
int v,d,n;
}

public
int top;
public
edge edges[];
public
int adj[];
public
int N;
public
Graph(int N_)
{

N=N_;
edges=new edge[(N-1)*2];
top=0;
adj=new int[N];
Arrays
.fill(adj,-1);
}

void
add_edge(int u,int v,int d)
{

u--;v--;
edges[top]=new edge();edges[top].v=v;edges[top].d=d;edges[top].n=adj[u];adj[u]=top++;
edges[top]=new edge();edges[top].v=u;edges[top].d=d;edges[top].n=adj[v];adj[v]=top++;
}
}

public
Graph graph;
public
long get_answer()
{

int
qh,qt;
int
q[]=new int[graph.N];
int
f[]=new int[graph.N];
int
d[]=new int[graph.N];
boolean
inq[]=new boolean[graph.N];
Arrays
.fill(inq,false);
inq[q[qh=qt=0]=0]=true;
while
(qh<=qt)
{

int
u=q[qh++];
for
(int e=graph.adj[u];e!=-1;e=graph.edges[e].n)
{

int
v=graph.edges[e].v;
if
(!inq[v])
{

inq[q[++qt]=v]=true;
f[v]=u;
d[v]=graph.edges[e].d;
}
}
}

long
answer=0;
int
c[]=new int[graph.N];
Arrays
.fill(c,0);
while
(qt>=0)
{

int
u=q[qt--];
c[u]++;
c[f[u]]+=c[u];
answer+=(long)(Math.min(c[u],graph.N-c[u]))*(long)(d[u])*(long)(2);
}

return
answer;
}

public
Main()
{

Scanner
cin = new Scanner(new BufferedInputStream(System.in));
int
T=cin.nextInt();
for
(int t=1;t<=T;t++)
{

int
N=cin.nextInt();
graph=new Graph(N);
for
(int i=1;i<N;i++)
{

int
X,Y,Z;
X=cin.nextInt();
Y=cin.nextInt();
Z=cin.nextInt();
graph.add_edge(X,Y,Z);
}

System
.out.println("Case #"+t+": "+get_answer());
}
}
}

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注