给出n个点的一个图,要求把所有点分成两部分,一部分是一个团,一部分是一个独立集.n<=5000
记录自己的愚蠢... 首先考虑如何判断存在可行方案,那么每个点要么属于团,要么属于独立集,且可以根据一个点属于哪一部分推出其他某些属于哪一部分.(如果我们钦定点A属于团,那么所有和A没有连边的点都必须属于独立集,如果我们钦定点A属于独立集,那么所有和A有连边的点都必须属于团).这样的二元关系相互推导的模型自然可以转化为2-SAT.点数5000,边数5000*5000,所以需要线性的做法,跑tarjan强联通分量. 然后我就不会怎么统计方案了,愚蠢*1 看题解,发现有个很妙的性质:假如我们有两个不同的方案都是合法的,那么不可能存在两个不同的点u,v使得这两个点在一个方案中都在独立集里,在另一个方案中都在团里.正确性是显然的,然而没有想到.这个结论虽然简单却非常有力:只需要找出任意一个可行解,那么其他可行解都可以由这个可行解进行次数不多的修改得到.(有三种情况:把独立集中的一个点拿到团里;把团里的一个点拿到独立集里;把团里的一个点和独立集里的一个点互换),那么我们枚举所有可能的修改情况即可. 然后我就把tarjan求强连通分量写错了.把x出栈后,我把in_stack[x]赋值为true...(应当赋值为false).愚蠢*2 过了样例交一发,然后WA了.愚蠢*3 发现有个if里的判断条件少加了一个!,意思全反了.改过来交,又WA了.愚蠢*4 发现我求出来的方案不一定两个集合都非空.改过来交,又WA了.愚蠢*5 发现我默认2SAT求出来的初始解两个集合都非空.改过来交,终于A了. 这做题状态不行啊...
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int maxn=10005,maxm=25000005; struct edge{ int to,next; }lst[maxm],lst2[maxm];int len=1,first[maxn],len2=1,first2[maxn]; void addedge(int a,int b){ lst[len].to=b;lst[len].next=first[a];first[a]=len++; } void addedge2(int a,int b){ lst2[len2].to=b;lst2[len2].next=first2[a];first2[a]=len2++; } int conv(int a,int t){ return (a<<1)|t; }//conv(a,1):a is spy conv(a,0):a is supply int n; bool E[maxn][maxn]; int dfn[maxn],T,stk[maxn],top,low[maxn],belong[maxn],tot; bool ins[maxn]; vector<int> scc[maxn]; void dfs(int x){ dfn[x]=low[x]=++T;ins[stk[top++]=x]=true; for(int pt=first[x];pt;pt=lst[pt].next){ if(!dfn[lst[pt].to]){ dfs(lst[pt].to); if(low[lst[pt].to]<low[x])low[x]=low[lst[pt].to]; }else if(ins[lst[pt].to]&&dfn[lst[pt].to]<low[x])low[x]=dfn[lst[pt].to]; } if(dfn[x]==low[x]){ ++tot; do{ ins[stk[--top]]=false; belong[stk[top]]=tot; scc[tot].push_back(stk[top]); }while(stk[top]!=x); } } bool twosat(){ for(int i=2;i<=2*n+1;++i){ if(!dfn[i])dfs(i); } for(int i=1;i<=n;++i){ if(belong[conv(i,0)]==belong[conv(i,1)])return false; } return true; } int col[maxn],scccol[maxn]; bool mark[maxn]; bool toposorted[maxn]; int seq[maxn],cnt; void toposort(int x){ if(toposorted[x])return; for(int pt=first2[x];pt;pt=lst2[pt].next){ toposort(lst2[pt].to); } seq[++cnt]=x;toposorted[x]=true; } void getsol(){ for(int i=2;i<=2*n+1;++i){ for(int pt=first[i];pt;pt=lst[pt].next){ if(belong[i]!=belong[lst[pt].to]){ addedge2(belong[i],belong[lst[pt].to]); } } } for(int i=1;i<=tot;++i)toposort(i); for(int i=1;i<=tot;++i){ int x=seq[i]; if(mark[x]&&scccol[x]==0)continue; mark[x]=true;scccol[x]=1; for(vector<int>::iterator pt=scc[x].begin();pt!=scc[x].end();++pt){ mark[belong[(*pt)^1]]=true;scccol[belong[(*pt)^1]]=0; } } } int cnt_anti[maxn],anti[maxn]; int main(){ scanf("%d",&n); for(int i=1,num,x;i<=n;++i){ scanf("%d",&num); while(num--){ scanf("%d",&x);E[i][x]=true; } } for(int i=1;i<=n;++i){ for(int j=i+1;j<=n;++j){ if(E[i][j]){ addedge(conv(i,1),conv(j,0)); addedge(conv(j,1),conv(i,0)); }else{ addedge(conv(i,0),conv(j,1)); addedge(conv(j,0),conv(i,1)); } } } if(!twosat())printf("0\n"); else{ getsol(); for(int i=1;i<=n;++i)col[i]=scccol[belong[conv(i,1)]]; //for(int i=1;i<=n;++i)printf("%d",col[i]); for(int i=1;i<=n;++i){ if(!col[i]){ for(int j=1;j<=n;++j){ if(col[j]&&E[i][j]){ anti[i]=j;cnt_anti[i]++; } } }else{ for(int j=1;j<=n;++j){ if((!col[j])&&(!E[i][j])){ anti[i]=j;cnt_anti[i]++; } } } } int num[2]={0,0}; for(int i=1;i<=n;++i)num[col[i]]++; int ans=(num[0]!=0&&num[1]!=0); for(int i=1;i<=n;++i){ if(cnt_anti[i]==0&&num[col[i]]!=1)ans++; } for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ if(col[i]&&(!col[j])){ if(cnt_anti[i]==0||(cnt_anti[i]==1&&anti[i]==j)){ if(cnt_anti[j]==0||(cnt_anti[j]==1&&anti[j]==i))ans++; } } } } printf("%d\n",ans); } return 0; }转载于:https://www.cnblogs.com/liu-runda/p/7157738.html
相关资源：数据结构—成绩单生成器