题意
给定N个三元组（ui，vi，wi），要求你建造一个树的数量最少的森林。对森林的要求如下：
（1）每个树是个有根树
（2）父边的边权比儿子边的边权小
（3）每个结点最多有m个儿子结点
（4）森林应恰好有N条边
输出最小的树的数量即可。
解题
对N条边按照边权升序排序。按照排好序后的边去遍历边，每次尝试将边（u，v）接到u结点的下面。为了满足第三个要求，用mp[u]表示u结点下还可以接的边数（注意到u的值最大有2e9，所以用map存）。O（n)级别遍历边并同时维护下mp[i]即可。
AC代码
#include <bits/stdc++.h>
using namespace std;const int maxn=1e5+7;
struct node
{int u,v,w;bool operator<(const node &o)const{return w<o.w;}
}a[maxn];
map<int,int> mp;int main()
{int n,m;while(cin>>n>>m){for(int i=1;i<=n;i++){int u,v,w;cin>>u>>v>>w;a[i].u=u,a[i].v=v,a[i].w=w;}sort(a+1,a+1+n);mp.clear();int ans=0;for(int i=1;i<=n;i++){int u=a[i].u,v=a[i].v;if(!mp[u]){ans++;mp[u]+=m;}mp[u]--;mp[v]+=m;}cout<<ans<<endl;}return 0;
}