新年的聚会
题目描述
解法
其实用分治的思想很容易解决聚会个数的限制，我们可以枚举一个点对其他点做分治，那么询问次数是 \(O(m\log n)\)，但是这样做总人数不满足条件。
关键结论：对于一个边数为 \(m\) 的图可以划分出 \(\sqrt m\) 个独立集。对于度数 \(\geq\sqrt m\) 的点可以单独划分成独立集，对于度数 \(<\sqrt m\) 的点，考虑邻接点颜色的 \(\tt mex\) 必然小于 \(\sqrt m\)，所以可以根据 \(\tt mex\) 确定它的颜色（颜色就是指独立集标号）
划分独立集可以对于每一个点枚举它划分在哪个独立集中，然后用 \(\tt meeting\) 函数检验。然后我们对于枚举两个独立集，用分治的方法来确定他们的边，也就是把较大的那个集合拆成两半，然后递归下去即可，出口就是两个集合大小都为 \(1\)
复杂度显然是说不清楚的，但是上面是一个平衡复杂度的做法，如果不够放心可以在划分独立集的时候把所有点 \(\tt random\_shuffle\) 一遍。
总结
图论问题常用度数 \(\sqrt m\) 分类的方法来平衡复杂度。
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include "meeting.h"
using namespace std;
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
const int M = 1005;
int cnt=0,p[M];
vector<pii> ans;vector<int> s[M];
void cdq(int x,int y,int xl,int xr,int yl,int yr)
{
if(xr-xl<yr-yl) swap(x,y),swap(xl,yl),swap(xr,yr);
if(xl==xr && yl==yr)
{
ans.pb(mp(s[x][xl],s[y][yl]));
return ;
}
int mid=(xl+xr)>>1;vector<int> A,B;
for(int i=yl;i<=yr;i++)
A.pb(s[y][i]),B.pb(s[y][i]);
for(int i=xl;i<=xr;i++)
i<=mid?A.pb(s[x][i]):B.pb(s[x][i]);
if(!meeting(A)) cdq(x,y,xl,mid,yl,yr);
if(!meeting(B)) cdq(x,y,mid+1,xr,yl,yr);
}
vector<pii> solve(int n)
{
srand(time(0));
for(int i=0;i<n;i++) p[i]=i;
random_shuffle(p,p+n);
for(int w=0;w<n;w++)
{
int fl=0,i=p[w];
for(int j=1;j<=cnt;j++)
{
s[j].pb(i);
if(meeting(s[j])) {fl=1;break;}
s[j].pop_back();
}
if(!fl) s[++cnt].pb(i);
}
for(int i=1;i<=cnt;i++)
for(int j=i+1;j<=cnt;j++)
{
int l1=s[i].size(),l2=s[j].size();
cdq(i,j,0,l1-1,0,l2-1);
}
return ans;
}