【LOJ】#2445. 「NOI2011」道路修建

题解

看完题目我的第一个反应是……要求最小花费的方案？！怎么求？？？

然后我把题读完了。好吧。

记录一下size就行，比NOIP普及组还要不如的题= =

代码

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <queue>

#include <cmath>

#define enter putchar('\n')

#define space putchar(' ')

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define eps 1e-7

#define MAXN 1000005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

	res = 0;char c = getchar();T f = 1;

	while(c < '0' || c > '9') {

		if(c == '-') f = -1;

		c = getchar();

	}

	while(c >= '0' && c <= '9') {

		res = res * 10 + c - '0';

		c = getchar();

	}

	res *= f;

}

template<class T>

void out(T x) {

	if(x < 0) {putchar('-');x = -x;}

	if(x >= 10) {

		out(x / 10);

	}

	putchar('0' + x % 10);

}

int N;

struct node {

	int to,next,val;

}E[MAXN * 2];

int sumE,head[MAXN],siz[MAXN];

int64 ans;

void add(int u,int v,int c) {

	E[++sumE].to = v;

	E[sumE].next = head[u];

	E[sumE].val = c;

	head[u] = sumE;

}

int dfs(int u,int fa) {

	siz[u] = 1;

	for(int i = head[u] ; i ; i = E[i].next) {

		int v = E[i].to;

		if(v != fa) {

			dfs(v,u);

			siz[u] += siz[v];

			ans += 1LL * E[i].val * abs(N - siz[v] - siz[v]);

		}

	}

}

void Solve() {

	read(N);

	int u,v,c;

	for(int i = 1 ; i < N ; ++i) {

		read(u);read(v);read(c);

		add(u,v,c);add(v,u,c);

	}

	dfs(1,0);

	out(ans);enter;

}

int main() {

#ifdef ivorysi

	freopen("f1.in","r",stdin);

#endif

	Solve();

}

巴特西

【LOJ】#2445. 「NOI2011」道路修建

题解

代码

最新文章

热门文章