题解 P5061 【秘密任务】

· · 题解

对于第 (1)(2) 问，可以求补图再二分图匹配 (不过出题人不会因此不讲这个)

加入第 (3) 问就是为了卡掉上面的解法，其是本蒟蒻也不知道是否可行

出题人的解法有点非常规，不保证没有其他解法：

因为只分两组，我们可以进行第一次求解，先把一个人放到第一组，第二组为空，然后重复迭代对剩下的人进行放置，直到进行了一次迭代却一个人也没有放置(仅放置方案唯一的人，若两组都可以放，那么就先保留)

于是我们保留下来了一些人，也知道了目前在第一组的人必须与第二组的人分开。

我们可以对保留下来的人继续处理，进行第二/三/四......次求解，先把一个人放到第一组......

最后我们把所有的人都放完，得到一些关系，即同一次求解中得到的两组人必须分开，不同次求解得到的小组可以随意混合(在上述前提下)。

可以这样描述：

有 A ，B 两个等长无负值的序列

现在把A ，B 中的值分成两组，每一组的权值和代表的就是人数， A[i] 和 B[i] 不能存在于同一组，求能得到的无序权值二元组不同的分组方案数和两组权值最接近的一种方案。

进行动态规划即可求解第 (1)(2) 问

对于第三问，利用刚刚提到的：

同一次求解中得到的两组人必须分开，不同次求解得到的小组可以随意混合(在上述前提下)。

就很容易求解了，我们可以标记每一个人属于第几次求解第几组，只要不在同一次求解的相反组就有可能分在同一组。

这个思想不是很好讲，我已经尽力了

考虑实现这个思想，我们使用 dfs，一次dfs负责同一次求解的迭代，一个dfs实现反复求解知道所有人都有了归属，因此最后是两个 dfs 互相调用......这对代码实现能力有一定要求。

时间复杂度？一次求解至少分配一个人，求解调用的 dfs 进行一次也一定分配至少一个人，否则就会回到求解过程，因此时间复杂度为O(N^2)

Code: 

#include<iostream>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
#define maxx(a,b) (a>b)?a:b
#define minx(a,b) (a<b)?a:b
#define mod 1000000007
inline int read()
{
    int q=0;
    char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
        q=q*10+c-'0',c=getchar();
    return q;
}
int matrix[2510][2510],s1[2510][2510],s2[2510][2510],tmp[2510],tmp1[2510][2510],tmp2[2510][2510],f[2510][2510],mem[710][2],data[2510*2500][2];
int n,m,pos,statistic,u,v,top,ans,max_ans;
void divide(int,int);
void solve(int[]);
void solve(int q[])
{
    if(!q[0])
        return;
    top++;
    s1[top][1]=q[1],s1[top][0]=1;
    mem[q[1]][0]=top,mem[q[1]][1]=1;
    for(register int i=2;i<=q[0];i++)
        tmp1[top][i-1]=q[i];
    tmp1[top][0]=q[0]-1;
    divide(top,2);
}

void divide(int x,int r)//x阶,放到哪 
{
    if(r==2)
    {
        bool flag=false;
        tmp2[x][0]=0;
        for(int i=1;i<=tmp1[x][0];i++)
        {
            pos=1;
            for(int j=1;j<=s1[x][0];j++)
                if(!matrix[tmp1[x][i]][s1[x][j]])
                {
                    pos=2;
                    flag=true;
                    break;
                }
            if(pos==2)  
            {
                for(int j=1;j<=s2[x][0];j++)
                    if(!matrix[tmp1[x][i]][s2[x][j]])
                    {
                        printf("-1\n%d",m);
                        exit(0);
                    }
                s2[x][++s2[x][0]]=tmp1[x][i],mem[s2[x][s2[x][0]]][0]=x,mem[s2[x][s2[x][0]]][1]=r;
            }
            else
                tmp2[x][++tmp2[x][0]]=tmp1[x][i];
        }
        if(flag)
            divide(x,1);
        else
            solve(tmp1[x]);
    }
    else
    {
        bool flag=false;
        tmp1[x][0]=0;
        for(int i=1;i<=tmp2[x][0];i++)
        {
            pos=2;
            for(int j=1;j<=s2[x][0];j++)
                if(!matrix[tmp2[x][i]][s2[x][j]])
                {
                    pos=1;
                    flag=true;
                    break;
                }
            if(pos==1)  
            {
                for(int j=1;j<=s1[x][0];j++)
                    if(!matrix[tmp2[x][i]][s1[x][j]])
                    {
                        printf("-1\n%d",m);
                        exit(0);
                    }
                s1[x][++s1[x][0]]=tmp2[x][i],mem[s1[x][s1[x][0]]][0]=x,mem[s1[x][s1[x][0]]][1]=r;
            }
            else
                tmp1[x][++tmp1[x][0]]=tmp2[x][i];
        }
        if(flag)
            divide(x,2);
        else
            solve(tmp2[x]);
    }
}

inline long long pow(int b,int p)
{
    long long g=1,base=b;
    while(p)
    {
        if(p&1)
            g*=base,g%=mod;
        p=p>>1,base*=base,base%=mod;
    }
    return g;
}

int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        u=read(),v=read();
        data[i][0]=u,data[i][1]=v;
        matrix[u][v]=matrix[v][u]=1;
    }
    for(int i=1;i<=n;i++)
        tmp[i]=i;
    tmp[0]=n;
    solve(tmp);
    f[0][0]=1;
    for(int i=1;i<=top;i++)//动态规划过程
        for(int j=n;j>=0;j--)
            f[i][j]|=(f[i-1][j-s1[i][0]]|f[i-1][j-s2[i][0]]);
    for(int i=n/2;i>=0;i--)
        if(f[top][i])
        {
            if(!max_ans)
                max_ans=i;
            ans++;
        }
   for(register int i=1;i<=m;i++)
        if(mem[data[i][0]][0]==mem[data[i][1]][0]&&mem[data[i][0]][1]!=mem[data[i][1]][1])
            statistic++;
    printf("%d %lld\n%d",ans,(pow(2,n-max_ans)-pow(2,max_ans)+mod)%mod,statistic);
    return 0;
}