P2170 选学霸

时间：2021-01-22 04:52:43

传送门

思路：

　　① 可以把每个学生都看作点，而那些实力相同的学生就处在同一个连通块内，因为连通块内的同学要么都取，要么不取，所以可以将连通块缩成一个点。只需用并查集维护每个连通块的大小。

　　② 接着采取神奇的可行性DP：用 f[ i ] 判断选出 i 个学生的方案是否可行。可行就转移 。

　　伪代码：

　　　　初始化： f[ 0 ] =true;

　　　　for( j: 1~n ) //枚举点

　　　　　　for( i: n-size ~0 ) //逆序，，

　　　　　　　　if( f[ i ] )

　　　　　　　　　　f [ i - size ] =true.( size 为枚举到的点大小）

　　③ 最后只要暴力地从 m 左右两边找出离 m 最近的  f[ i ] == true，就是答案。

Code：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<cstdlib>

#include<stack>

#include<vector>

#include<queue>

#include<deque>

#include<map>

#include<set>

using namespace std;

#define lck_max(a,b) ((a)>(b)?(a):(b))

#define lck_min(a,b) ((a)<(b)?(a):(b))

typedef long long LL;

const int maxn=4e5+;

inline LL lck_abs(LL a) {return a>?a:-a;}

inline LL read()

{

    LL kr=,xs=;

    char ls;

    ls=getchar();

    while(!isdigit(ls))

    {

        if(!(ls^))

            kr=-;

        ls=getchar();

    }

    while(isdigit(ls))

    {

        xs=(xs<<)+(xs<<)+(ls^);

        ls=getchar();

    }

    return xs*kr;

}

inline void out(LL xs)

{

    if(!xs) {putchar(); return;}

    if(xs<) putchar('-'),xs=-xs;

    int kr[],ls=;

    while(xs) kr[++ls]=xs%,xs/=;

    while(ls) putchar(kr[ls]+),ls--;

}

LL fa[maxn],si[maxn];//si 维护连通块大小

inline LL find(LL u)

{

    return fa[u]==u?fa[u]:find(fa[u]);

}

LL n,m,k,u,v,i,j,l,r,ans,top,st[maxn];bool f[maxn];

int main()

{

    n=read();m=read();k=read();

    for(i=;i<=n;i++)

        fa[i]=i,si[i]=;

    for(i=;i<=k;i++)

    {

        u=read();v=read();

        LL r1=find(u),r2=find(v);

        if(r1==r2) continue;

        fa[r2]=r1,si[r1]+=si[r2];

    }

    for(LL i=;i<=n;i++)

        if(fa[i]==i) st[++top]=i;//缩点

    f[]=true;

    for(i=;i<=top;i++)//枚举点

        for(j=n-si[st[i]];j>=;j--)//可达性DP

            if(f[j])

                f[j+si[st[i]]]=true;

    for(i=m;!f[i];i--); l=m-i;//找到比m小的最接近的人数

    for(i=m;!f[i];i++); r=i-m;//找到比m大的最接近的人数

    if(r>=l) out(m-l),putchar('\n');

    else out(m+r),putchar('\n');

return ;

}

相关文章