题目大意
有个(n)个点(m)条边的图。
要找到一个最小度数为(p)的子图和(q)个互不相连的点，使(pgeqlfloorfrac{n}{q+1}
floor)且(qgeqlfloorfrac{n}{p+1}
floor)。
(nleq 10^4;mleq 10^5;数据组数leq32;)
题解
题目的条件中把分母乘过去，会发现需要(p imes q)尽可能大。
(p,q)的大小看上去没什么关系，就相当于让它们分别尽可能大。
使(p)尽可能大：发现只有删掉当前的图中度数最小的点，才能使最小度数增加。所以每次删掉当前图中度数最小的点，并更新度数，记下最大的最小度数出现在第几次。
使(q)尽可能大：“最大点独立集”是个np问题，但这题没必要“最大”，只要大于(lfloorfrac{n}{p+1}
floor)就行。可以每次选出度数最小的点加入点集，删去与它相连的点。如果删去的点数（即度数最小的点的度数）大于(p)，那么删之前所有点的度数都大于(p)，那么(p)就不是最大的了。之前第一问的做法保证了(p)最大，所以每次删的点数不大于(p)，加入点集的点数(q imes (p+1)geq n)。
这两问中用可删堆容易超时，发现两问中都是一个点只会被删一次，开数组记录已经被删的点就行了。
代码
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define rep(i,x,y) for(register int i=(x);i<=(y);++i)
#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)
#define view(u,k) for(int k=fir[u];~k;k=nxt[k])
#define maxn 10007
#define maxm 200007
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-')ch=getchar();
if(ch=='-')f=-1,ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return x*f;
}
void write(int x)
{
if(x==0){putchar('0'),putchar(' ');return;}
int f=0;char ch[20];
if(x<0)putchar('-'),x=-x;
while(x)ch[++f]=x%10+'0',x/=10;
while(f)putchar(ch[f--]);
putchar(' ');
return;
}
int t,n,m,fir[maxn],nxt[maxm],v[maxm],cnte,ord[maxn],vis[maxn],d[maxn],tp,pos,mx;
priority_queue<pii >q;
void ade(int u1,int v1){v[cnte]=v1,nxt[cnte]=fir[u1],fir[u1]=cnte++;}
int main()
{
t=read();
while(t--)
{
n=read(),m=read();
rep(i,1,n)fir[i]=-1,d[i]=ord[i]=vis[i]=0;cnte=mx=pos=tp=0;
rep(i,1,m){int x=read(),y=read();ade(x,y),ade(y,x),d[x]++,d[y]++;}
rep(i,1,n)q.push(mp(-d[i],i));
while(!q.empty())
{
int u=q.top().se,su=-q.top().fi;q.pop();if(vis[u])continue;
vis[u]=1;ord[++tp]=u;if(!pos||mx<su)pos=tp,mx=su;
view(u,k)if(!vis[v[k]]){d[v[k]]--;q.push(mp(-d[v[k]],v[k]));}
}
write(n-pos+1);rep(i,pos,n)write(ord[i]);puts("");
tp=0;rep(i,1,n)q.push(mp(-d[i],i)),vis[i]=0;
while(!q.empty())
{
int u=q.top().se;q.pop();if(vis[u])continue;
vis[u]=1;ord[++tp]=u;
view(u,k)vis[v[k]]=1;
}
write(tp);rep(i,1,tp)write(ord[i]);puts("");
}
return 0;
}
奇怪的思路
把每个点编为与周围染好的点不同的编号最小的编号。
第一问取编号恰为1~最大编号的点，第二问取数量最多的同一编号的点（数量一定大于(lfloorfrac{n}{编号数+1}
floor)）。
但是最大编号和进行编号的顺序有关，有的图能通过不巧的编号顺序增大最大编号，所以这个方法是错的（或者说我不知道能不能修）。
这个方法只有10分，第一问无脑输出所有点（loj数据）都有80分。