题解 P2175 【小Z的游戏分队】

· · 题解

以不信任关系建图

二分图判定染色

cnt[i][0/1]表示第i个连通块染1/0颜色的个数

f[i][j]表示前i个连通块第一个集合点的个数减第二个集合点的个数等于j是否可以达到（注意j可能为负 #define f(i,j) dp[i][j+2000]）

f(i,j)|=f(i-1,j-cnt[i][0]+cnt[i][1])| f(i-1,j+cnt[i][0]-cnt[i][1]) 对于第i个连通块两种情况：

（1） 颜色为1 的点放入第1个集合，颜色为2 的点放入第2个集合

（2） 颜色为1 的点放入第2个集合，颜色为2 的点放入第1个集合

PS:这里解释一下为什么这道题不能用Tarjan强连通分量，因为信任关系不具有传递性。

#include <cstdio>
#include <iostream>
using namespace std;
const int N=2005;
int n,x,m,color[N],cnt[N][3],f[N][N+N];
bool flag[N][N];
int tot,head[N],next[N*N],adj[N*N];
inline int read(int &x){
    char c=getchar();int num=0;
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar()) num=(num<<1)+(num<<3)+c-'0';
    x=num;
}
void addedge(int u,int v){
    ++tot;
    next[tot]=head[u];
    head[u]=tot;
    adj[tot]=v;
}
bool dfs(int u){//二分图染色
    if(color[u]==1) cnt[m][1]++;
    else cnt[m][2]++;
    int e,v;
    for(e=head[u];e;e=next[e]){
        v=adj[e];
        if(!color[v]){
            color[v]=3-color[u];
            dfs(v);
        }
        else if(color[v]!=3-color[u]) return false;
    }
    return true;
}
int main(){
    read(n);
    for(int i=1;i<=n;i++)
        while(1){
            read(x);
            if(x==0) break;
            flag[i][x]=true;
        }
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(!flag[i][j]||!flag[j][i]){
                addedge(i,j);
                addedge(j,i);
            }
    for(int i=1;i<=n;i++)
        if(!color[i]){
            ++m;
            color[i]=1;
            if(!dfs(i)){
                printf("No solution");
                return 0;
            }
        }
    f[0][0]=1;
    for(int i=1;i<=m;i++)
        for(int j=-2000;j<=2000;j++)//枚举第一个集合点的个数与第二个集合点的差值
            f[i][j+2000]|=f[i-1][j-cnt[i][1]+cnt[i][2]+2000]|f[i-1][j+cnt[i][1]-cnt[i][2]+2000];
    int x,y;
    for(int j=0;j<=2000;j++)
        if(f[m][j+2000]||f[m][j]){ //枚举第一个集合点的个数与第二个集合点的差的绝对值
            x=(n+j)/2;
            y=n-x;
            if(x>y) swap(x,y);
            printf("%d %d\n",x,y);
            return 0;
        }
    printf("No solution");
    return 0;
}