构造题
解题思路
贪心。优先满足想交朋友数最多的人。每次排序，让能交朋友多的人分别和第二，第三，……，交朋友。
代码实现
循环进行贪心分配。每次循环先排序，再分配朋友并更新需求。
代码
#include<bits/stdc++.h>
using namespace std;
int n;
bool f[1010][1010];
struct node{int v,id;friend bool operator <(node a,node b){return a.v>b.v;}
}a[1010];
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i].v,a[i].id=i;for(int i=1;i<=n;i++){sort(a+1,a+n+1);for(int j=2;j<=a[1].v+1;j++){if(!a[j].v)return cout<<"NO SOLUTION"<<endl,0;a[j].v--;f[a[1].id][a[j].id]=1;f[a[j].id][a[1].id]=1;}a[1].v=0;}cout<<"SOLUTION\n";for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(f[i][j])cout<<j<<' ';}cout<<endl;}return 0;
}
发散思考
线性的问题能不能转化到树上？
考虑下列问题：
- 给定 \(n\) 个点的树，问能选出多少点对 \((u,v)\)，满足 \(u,v\) 互相不为祖先，每个点只能被包含在一个点对中。
这个问题将线性转化到了树上。
由调整法，若所有子树的大小均不超过它们总大小的一半，根据经典的结论可知，匹配数能够达到上界。
否则，记大小最大的子树是 \(v\)，由调整法可知，存在一种最优方案使所有子树之间的匹配，存在于 \(v\) 和其它子树之间。那么我们只需优先在 \(v\) 的子树内部匹配，之后将剩余节点与其它子树匹配。