开办了一家电话公司。他雇用了
个职员,给了每个职员一部手机。每个职员的手机里都存储有一些同事的
电话号码。由于的公司规模不断扩大,旧的办公楼已经显得十分狭窄,FGD决定将公司迁至一些新的办公楼。
希望职员被安置在尽量多的办公楼当中,这样对于每个职员来说都会有一个相对更好的工作环境。但是,为了联
系方便起见,如果两个职员被安置在两个不同的办公楼之内,他们必须拥有彼此的电话号码。
第一行包含两个整数和
。职员被依次编号为
.以下
行,每
行包含两个正数和
,表示职员
和
拥有彼此的电话号码),
包含两行。第一行包含一个数,表示
最多可以将职员安置进的办公楼数。第二行包含
个从小到大排列的
数,每个数后面接一个空格,表示每个办公楼里安排的职员数。
7 16 1 3 1 4 1 5 2 3 3 4 4 5 4 7 4 6 5 6 6 7 2 4 2 7 2 5 3 5 3 7 1 7
3 1 2 4
可以将职员
安排进一号办公楼,职员
和职员
安排进
号办公楼,其他人进
号办公楼。
做题历程:如果大家跟我一样的话……就会发现这道题建完图之后就一点儿也没有头绪的有木有!?!因为……貌似毫无规律,但其实,是有的,考虑建这个图的补图,不难猜出结论:答案就是这张图的补图的联通快的个数和每个联通块内点的个数。这里补图的定义是:给图中没有连边的两个点连上边,有连边的点不连边。
为什么呢?因为答案要求最大,那么任意没有联系方式的两人肯定要在一栋楼里面,因此,按补图建完后,恰好符合这个条件,且结果一定最大,因为只有没有联系方式的人才会在一栋楼里面,恰好满足条件,但是,一看这个数据范围。。方建补图肯定是不可行的啊。。那怎么办呢?
思路:考虑怎么求补图的联通块信息,具体流程如下:
先将所有的点加入链表
然后从链表中随便拿出一个点加入队列,如果链表为空,结束
遍历当前队列
对于当前点,把它的连接的边打上标记。
遍历链表,取出没有打标记的点从链表中删去并加入队列。
取消标记。
在每次进入队列的点统计为一个连通块。
这样用链表+队列统计答案的话,时间复杂度为。
参考代码:
#include<cstdio> #include<algorithm> #include<cctype> #define maxn 2000007 using namespace std; int n,m,q[maxn],l,r,head[maxn],num,pre[maxn],nxt[maxn],ans[maxn],cnt; bool vis[maxn]; int qread() { char c=getchar();int num=0,f=1; for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f; } struct node { int v,nxt; }e[maxn<<1]; inline void ct(int u, int v) { e[++num]=(node){v,head[u]}; head[u]=num; } int main() { n=qread(),m=qread(); for(int i=1,u,v;i<=m;++i) { u=qread(),v=qread(); ct(u,v),ct(v,u); } for(int i=1;i<=n;++i) pre[i]=i-1,nxt[i]=i+1; nxt[0]=1,nxt[n]=0; while(nxt[0]) { l=1,r=0; q[++r]=nxt[0]; nxt[0]=nxt[nxt[0]]; pre[nxt[q[r]]]=0; while(l<=r) { int u=q[l++]; for(int i=head[u];i;i=e[i].nxt) vis[e[i].v]=1; int p=nxt[0]; while(p) { if(!vis[p]) { q[++r]=p; pre[nxt[p]]=pre[p]; nxt[pre[p]]=nxt[p]; } p=nxt[p]; } for(int i=head[u];i;i=e[i].nxt) vis[e[i].v]=0; } ans[++cnt]=l-1; } sort(ans+1,ans+1+cnt); printf("%d\n",cnt); for(int i=1;i<=cnt;++i) printf("%d ",ans[i]); puts(""); return 0; }