802
cf 158div2 D. Black and White Tree
题意很简单，给出一个树中每个点相连的边的权值和，和点的颜色，一条边上颜色不同，求出原图……
因为条件很少，所以必然是个spj，所以可以直接贪心，然后把最后剩余的0边挂到任意一点上即可
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define INF 1E9
using namespace std;
#define mp make_pair
#define f first
#define s second
vector<pair<int,int> >v[2];
int main()
{
int n,i,j,k,t;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d%d",&t,&k);
v[t].push_back(mp(k,i+1));
}
sort(v[0].begin(),v[0].end());
sort(v[1].begin(),v[1].end());
for(i=j=0;i<v[0].size()&&j<v[1].size();)
{
k=min(v[0][i].f,v[1][j].f);
printf("%d %d %d\n",v[0][i].s,v[1][j].s,k);
v[0][i].f-=k;v[1][j].f-=k;
if(v[0][i].f)j++;
else if(v[1][j].f)i++;
else if(i<v[0].size()-1)i++;
else j++;
}
return 0;
}
最后更新：2017-04-04 07:03:16