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; }
上一篇: STL中的函数对象实现负数的定义
下一篇: 胃痛胃胀气 揉这几个穴位立即缓解