Codeforces 260D - Black and White Tree

本文主要是介绍Codeforces 260D - Black and White Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://codeforces.com/problemset/problem/260/D

题意： 有n个点的一个树，同一条边的两个点涂成不同的颜色(black & white)，每条边有一个权值，题目给出n ， 和每个点的颜色 和 与每个点相连的边的权值和。

求出n-1条边 的端点和权值。

n的 大小  10e5.  这有是一个构造的 题目。

由于题目说明 肯定可以构造出来， 所以，白色点的权值和的 总和 == 黑色点的权值和的 总和 。

可以分别把白色点 和黑色点  按照 权值和大小 排序。 然后分别从 两堆点中，取出最小两个点，这两点连边，权值为 两者的min， 之后两点的权值和分别减去 这个min，把权值为0的点delete, 直到处理完 n-1个点。 （注意，如果取出两个点 的权值都为0 的情况）

code: 

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
#define INF 1000000000
#define N 100005
int ad1,ad2,n;
struct node
{int su,id;
};
struct node a[N],b[N];
bool cmp(struct node x,struct node y)
{return x.su<y.su;
}
int main()
{scanf("%d",&n);int col,su;ad1=ad2=0;for(int i=1;i<=n;i++){scanf("%d%d",&col,&su);if(col){a[++ad1].su=su;a[ad1].id=i;}else{b[++ad2].su=su;b[ad2].id=i;}}sort(a+1,a+1+ad1,cmp);sort(b+1,b+1+ad2,cmp);for(int i=1,j=1;i<=ad1 && j<=ad2;){int tmp=min(a[i].su,b[j].su);printf("%d %d %d\n",a[i].id,b[j].id,tmp);a[i].su-=tmp; b[j].su-=tmp;if(a[i].su) j++;else if(b[j].su) i++;else if(i<ad1) i++;else j++;}return 0;
}

这篇关于Codeforces 260D - Black and White Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---