【BZOJ 3714】[PA2014] Kuglarz

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3714

首先我们可以得到一个结论:如果知道了每一个点的前缀和,那么我们就知道了答案
其次我们又可以知道:假如我们知道了sum(i-j)那么这两个点的前缀和可以知二推一
换一句话来说,第i个点和第j个点结合了起来
考虑什么时候可以得出答案:当所有点的前缀和都结合起来以后
然后就成了求一个最小生成树辣!

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2000+9;
const int M = N * N;

int n,m,fa[N]; LL vout;
struct Edge{
	int u,v,w;
	inline bool operator < (const Edge &B) const {
		return w < B.w;
	}
}edge[M];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline int find(int w) {
	int f = fa[w], tmp;;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp = fa[w], fa[w] = f, w = tmp;
	return f; 
}

int main(){
	n = read();
	for (int i=1;i<=n+1;i++) {
		fa[i] = i;
	}	
	for (int j=1;j<=n;j++) {
		for (int i=j;i<=n;i++) {
			edge[++m].u = j;
			edge[m].v = i + 1;
			edge[m].w = read();
		}
	}
	sort(edge+1,edge+1+m);
	for (int i=1;i<=m;i++) {
		if (find(edge[i].u) != find(edge[i].v)) {
			fa[fa[edge[i].u]] = fa[edge[i].v];
			vout += edge[i].w;
		}
	}
	printf("%lld\n",vout);
	return 0;
}

2 thoughts to “【BZOJ 3714】[PA2014] Kuglarz”

  1. Thank you for sharing superb informations. Your web site is very cool. I’m impressed by the details that you have on this website. It reveals how nicely you understand this subject. Bookmarked this web page, will come back for extra articles. You, my friend, ROCK! I found just the information I already searched everywhere and just couldn’t come across. What a great website.

  2. Heya i am for the primary time here. I came across this board and I in finding It truly helpful & it helped me out a lot. I hope to provide one thing again and aid others like you helped me.

Leave a Reply

Your email address will not be published. Required fields are marked *