欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

bzoj2215 POI2011 Conspiracy

程序员文章站 2022-06-10 19:58:37
题意 给出一张图,将其分为一个团和一个独立集。问有多少种方案。**团和独立集都不能为空** 思路 **先考虑找可行方案应该怎么做** ......

题意

给出一张图,将其分为一个团和一个独立集。问有多少种方案。团和独立集都不能为空

思路

先考虑找可行方案应该怎么做

显然是个\(2-sat\)。可以将分到团和独立集中分别看为0和1。

如果两个点之间右边,那么必定不能同时在独立集中。如果两个点之间没有边,那么必定不能同时在团中。然后连边\(求2-sat\)即可

然后考虑统计方案

可以发现,如果在某个可行方案中两个点都在团中,那么在所有方案中必定不能同时在独立集中。同样,如果两个点在某个个可行方案中都在独立集中,那么在所有方案中必定不能同时出现在团中。

这说明,一个可行方案调整到另一个可行方案时,最多有一个点从团中到了独立集中。也最多有一个点,从独立集中到了团中。

我们可以通过对上面的可行方案进行调整得到所有方案。

注意题目中要求团和独立集都不能为空

代码

/*
* @author: wxyww
* @date:   2019-05-02 14:03:51
* @last modified time: 2019-05-02 15:35:29
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int n = 5010;
#define ote(x) x > n ? x - n : x + n
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
vector<int>e[n << 1],tmp[n],c[2];
int n,a[n][n];
int val[n << 1],dfn[n << 1],low[n << 1],tot,vis[n << 1],sta[n << 1],top,coljs,col[n << 1];
void tarjan(int u) {
    int k = e[u].size();
    dfn[u] = low[u] = ++tot;
    vis[u] = 1;sta[++top] = u;
    for(int i = 0;i < k;++i) {
        int v = e[u][i];
        if(!dfn[v]) {
            tarjan(v);low[u] = min(low[u],low[v]);
        } 
        else if(vis[v]) low[u] = min(low[u],low[v]);
    }
    if(dfn[u] == low[u]) {
        ++coljs;
        do {
            int x = sta[top--];
            col[x] = coljs;
            vis[x] = 0;
        }while(sta[top + 1] != u);
    }
}
int main() {
    n = read();
    for(int i = 1;i <= n;++i)
        for(int j = 1,x = read();j <= x;++j) 
            a[i][read()] = 1;
    for(int i = 1;i <= n;++i) {
        for(int j = i + 1;j <= n;++j) {
            if(a[i][j]) {
                e[i].push_back(j + n);
                e[j].push_back(i + n);
            }
            else {
                e[i + n].push_back(j);
                e[j + n].push_back(i);
            }
        }
    }

    for(int i =  1;i <= n + n;++i) if(!dfn[i])  tarjan(i);

    for(int i = 1;i <= n;++i) 
        if(col[i] == col[i + n]) {
            puts("0");return 0;
        }

    for(int i = 1;i <= n;++i) {
        val[i] = col[i] < col[ote(i)];//0为团中,1为独立集中
        c[val[i]].push_back(i);
    }

    for(int i = 1;i <= n;++i) {
        for(int j = 1;j <= n;++j) {
            if(val[i] == val[j]) continue;
            if(val[i] ^ a[i][j]) tmp[i].push_back(j);
        }
    }

    int k1 = c[0].size(),k2 = c[1].size();
    int ans = k1 && k2;

    for(int i = 0;i < k1;++i) {
        int x = c[0][i],z1 = tmp[x].size();
        if(z1 > 1) continue;
        for(int j = 0;j < k2;++j) {
            int y = c[1][j],z2 = tmp[y].size();
            if(z2 > 1) continue;
            if((!z1 && !z2) || (!z1 && tmp[y][0] == x) || (!z2 && tmp[x][0] == y) || (tmp[x][0] == y && tmp[y][0] == x))
                ans++;
        }
    }

    for(int i = 1;i <= n;++i) 
        if(!tmp[i].size() && c[val[i]].size() > 1) ans++;

    cout<<ans;
    return 0;
}