题解 P5061 【秘密任务】

· · 题解

解题思路

　　orz出题人的神仙做法。本蒟蒻看不懂，就水个求补图再二分图染色的方法来%1%出题人。 　　

　　首先我们对图中m个关系连边，发现这样是没法做的，因为我们最后要关注的是谁和谁不能在一起，这个限制是比较大的。所以我们考虑建一个补图，就是把原来没有的边加边，原来存在的边断掉。这样a和b之间有边就代表a与b不能属于一个集合，这样就可能形成了若干个图。首先考虑判合法，因为一共只有两个集合，而每个人都必须放到集合里，关系还可以抽象成一张无向图，自然可以想到二分图染色了。我们只需要遍历每一个联通块，然后进行黑白染色判是否合法，只要有一个联通块不合法，那么也就GG了。

　　然后考虑算答案，判完合法之后，我们就可以知道一个了联通块中黑色和白色的不能属于一个集合，剩下的可以任意搭配，所以做一个背包就行了，把每个联通块黑色白色的个数记下来。设f[i]表示一个集合有i个人是否成立，转移的时候就模仿0/1背包，就是看每一个联通块是选黑色进去还是选白色进去。做完背包后一个人数合法仅当f[i]=f[n-i]=true。这样第一问和第二问的答案就统计出来了，对于第三问的答案，然后n^2枚举一下每对，如果两个人属于同一个联通块但颜色不相同，并且两个人在补图里没边，就使ans3++，这个也比较好理解，具体实现看代码。 　　

　　打波广告

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;
const int MAXN = 2505;
const int MOD = 1e9+7;
typedef long long LL;

inline int rd(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) f=ch=='-'?0:1,ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return f?x:-x;
}

int n,m,a[MAXN][MAXN],tot,num,cnt1,cnt2,ans1,ans2,ans3;
int w[MAXN][2],f[MAXN],now[MAXN],col[MAXN],Min;
bool flag;

void dfs(int x,int c){
    col[x]=c;now[++tot]=x;if(c==1) cnt1++;else cnt2++;
    for(int i=1;i<=n;i++)
        if(a[i][x]){
            if(col[i]==col[x]) {flag=1;return;}
            if(!col[i]) dfs(i,3-c); 
        }
}

inline int fast_pow(int x,int y){
    int ret=1;
    for(;y;y>>=1){
        if(y&1) ret=(LL)ret*x%MOD;
        x=(LL)x*x%MOD;
    }
    return ret;
}

int main(){
    int x,y;n=rd(),m=rd();
    for(int i=1;i<=m;i++){
        x=rd(),y=rd();
        a[x][y]=a[y][x]=1;
    }
    for(int i=1;i<=n;i++)   
        for(int j=1;j<=n;j++)
            if(i!=j) a[i][j]^=1;
    for(int i=1;i<=n;i++) if(!col[i]){
        cnt1=cnt2=tot=0;memset(now,0,sizeof(now));
        dfs(i,1);if(flag) break;
        for(int j=1;j<=tot;j++)
            for(int k=j+1;k<=tot;k++)
                if(col[now[j]]!=col[now[k]] && !a[now[j]][now[k]]) ans3++; 
        w[++num][0]=cnt1;w[num][1]=cnt2;
    }f[0]=1;
    for(int i=1;i<=num;i++){
        Min=min(w[i][0],w[i][1]);
        for(int j=n;j>=Min;j--){
            if(j>=w[i][0]) f[j]|=f[j-w[i][0]];
            if(j>=w[i][1]) f[j]|=f[j-w[i][1]];  
        }   
    }
    for(int i=0;i<=n/2;i++){
        if(!f[i] || !f[n-i]) continue;
        ans1++;ans2=i;
    }
    if(flag) puts("-1"),ans3=m; //注意一下这里，如果没有方案的话自然$m$对可以合作的人都无法在一个集合里
    else printf("%d %d\n",ans1,(fast_pow(2,n-ans2)-fast_pow(2,ans2)+MOD)%MOD);
    printf("%d\n",ans3);
    return 0;
}