注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

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

2011-11-11 16:44:34|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
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());
}
}
}
  评论这张
 
阅读(529)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018