首页 > 代码库 > bzoj2435 [Noi2011]道路修建
bzoj2435 [Noi2011]道路修建
Description
在 W 星球上有 n 个国家。为了各自国家的经济发展，他们决定在各个国家
之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬，他们只愿
意修建恰好 n – 1条双向道路。 每条道路的修建都要付出一定的费用， 这个费用等于道路长度乘以道路两端的国家个数之差的绝对值。例如，在下图中，虚线所示道路两端分别有 2 个、4个国家，如果该道路长度为 1，则费用为1×|2 – 4|=2。图中圆圈里的数字表示国家的编号。
.jpg)
由于国家的数量十分庞大，道路的建造方案有很多种，同时每种方案的修建
费用难以用人工计算，国王们决定找人设计一个软件，对于给定的建造方案，计
算出所需要的费用。请你帮助国王们设计一个这样的软件。
Input
输入的第一行包含一个整数n，表示 W 星球上的国家的数量，国家从 1到n
编号。接下来 n – 1行描述道路建设情况，其中第 i 行包含三个整数ai、bi和ci，表
示第i 条双向道路修建在 ai与bi两个国家之间，长度为ci。
Output
输出一个整数，表示修建所有道路所需要的总费用。
Sample Input
6
1 2 1
1 3 1
1 4 2
6 3 1
5 2 1
Sample Output
20
HINT
n = 1,000,000 1≤ai, bi≤n
0 ≤ci≤ 10^6
这是模拟题啊……
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define pi 3.1415926535897932384626433832795028841971using namespace std;inline LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}struct edge{int to,next,v;}e[2000010];struct bian{int x,y,z;}b[1000010];int n,m,cnt;int head[1000010];bool mrk[1000010];int fa[1000010];int son[1000010];LL ans;inline void ins(int u,int v,int w){ e[++cnt].to=v; e[cnt].v=w; e[cnt].next=head[u]; head[u]=cnt;}inline void insert(int u,int v,int w){ ins(u,v,w); ins(v,u,w);}inline void dfs(int x){ if (mrk[x])return;mrk[x]=1; son[x]=1; for (int i=head[x];i;i=e[i].next) if (!mrk[e[i].to]) { fa[e[i].to]=x; dfs(e[i].to); son[x]+=son[e[i].to]; }}int main(){ n=read(); for (int i=1;i<n;i++) { b[i].x=read();b[i].y=read();b[i].z=read(); insert(b[i].x,b[i].y,b[i].z); } dfs(1); for (int i=1;i<n;i++) { int x=b[i].x,y=b[i].y; if (fa[y]==x)swap(x,y); ans+=(LL)abs(son[x]-(n-son[x]))*b[i].z; } printf("%lld\n",ans);}
bzoj2435 [Noi2011]道路修建
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。