题解 CF755F 【PolandBall and Gifts】

· · 题解

看完题目，很自然的可以想到，每一个人给别人送礼物，就是连出去一条有向边
形成了一个n个点，n条边的有向图 观察一波性质 ，发现该图不一定连通，而且会形成若干个环

首先我们来看最大化收不到礼物的人数
对于每一个环，设环中节点数为k，则： 对于一个偶环，只要有\frac{k}{2}个人没带礼物，这k个人就都收不到礼物
对于一个奇环，只要有\frac{k+1}{2}个人没带礼物，这k个人就都收不到礼物
一个人不带礼物最多可以影响到两个人，所以我们先把这样的人的数量统计出来
也就是\sum \lfloor \frac{c[i]}{2} \rfloor 其中c[i]为环中节点个数
如果这样的人数大于等于忘带礼物的人数m，说明答案就是2\times m
否则，就先把这样的人的人全用了，不够的再用 那些奇环中影响不到别人（也就数奇环中多出来的那些单个的）的人补上

然后，来看最小化

对于一个大小为k的环，只要让这k个人都忘带礼物，他们就都收不到礼物 废话
所以，如果能找到若干个环，使得环中节点数之和恰好等于m，答案就是m
否则，忘带礼物的人的形式就是若干个环加上一条链，而这条链的尾部会有一个虽然带了礼物，但是收不到礼物的人。所以答案就是m+1

TLE！！

我们发现这样用01背包计算，时间复杂度是O(n\times m)的
这时，我们就要用到二进制分组来优化
因为，这个有向图中有可能有多个大小一样的环，所以这题其实本质是个多重背包
我们把大小同样的环二进制分组后，时间复杂度就降为了O(nlog_2n)，就可以AC辣

#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
const int Maxn=1000010,inf=0x3f3f3f3f;
int e[Maxn],f[Maxn],c[Maxn],a[Maxn];
int bin[Maxn];
bool vis[Maxn];
int n,m,ans,tot;
inline int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&& ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
    return s*w;
}
void bfs(int s)
{
    queue <int> q;
    q.push(s);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        f[x]=s,c[s]++;
        int y=e[x];
        if(!f[y])q.push(y);
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    n=read(),m=read();
    for(int i=1;i<=n;++i)
    e[i]=read();
    for(int i=1;i<=n;++i)
    if(!f[i])
    {
        bfs(i);
        bin[c[i]]++;
        ans+=(c[i]>>1);//注意一定要在二进制分组之前统计，不然就不能达到在奇环的时候的向下取整的效果了
    }
    for(int i=1;i<=n;++i)
    {
        if(!bin[i])continue;
        for(int j=1;bin[i]>=j;j<<=1)
        a[++tot]=j*i,bin[i]-=j;
        if(bin[i])a[++tot]=bin[i]*i;
    }
    vis[0]=1;
    for(int i=1;i<=tot;++i)
    {
        for(int j=m-a[i];j>=0;--j)
        if(vis[j])vis[j+a[i]]=1;
    }
    if(vis[m])printf("%d ",m);
    else printf("%d ",m+1);
    if(ans>=m)printf("%d\n",m<<1);
    else printf("%d\n",(ans<<1)+min(m-ans,n-(ans<<1))); //如果不够就找人去补
    //注意！最后收不到礼物的人数不能超过 n !!!
    return 0;
}