POJ1904 King's Quest 二分图+强连通分量
题目大意:
给定一个二分图以及一组已知的完备匹配,要求对于每个\(X\)集合中的点确定这个点与哪些个\(Y\)集合中的点匹配时,依然能够存在完备匹配.
思路:
考虑完备匹配中,\(X_i->Y_i,X_j->Y_j\),那么如果现在想要\(X_i->Y_j\),那么就要保证这样做之后从\(X_j\)出发存在增广路,否则就不能形成完备匹配.
那么这条增广路的终点显然应该是\(Y_i\),也即存在必定存在路径\(X_j->Y_i\).
我们考虑将之前给出的完备匹配的反向边连回去:即若存在匹配\(X_i->Y_i\),则连接有向边\(Y_i->X_i\).
那么我们考虑有路径\(X_j->Y_i->X_i->Y_j->X_j\),就是说形成了一个环,那么这些点必定在一个强连通分量中!
考虑与某个点\(X_i\)在一个强连通分量一些\(Y\)集合的点\(Y_k\),若存在边\(X_i->Y_k\),那么就是说\(Y_k\)要么是\(X_i\)原来的完备匹配,要么可以通过交换重新找到增广路得到完备匹配.
因此我们求一次SCC就解决了这道题目.
#define _CRT_SECURE_NO_WARNINGS #include<cstdio> #include<cstring> #include<climits> #include<iostream> #include<algorithm> #define N 2010 namespace Fio{ inline int getc(){ #ifdef ONLINE_JUDGE static const int L=1<<15; #else static const int L=1<<1; #endif static char buf[L],*S=buf,*T=buf; if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;} return*S++; } inline bool digit(int c){return c>='0'&&c<='9';} template<typename T>inline void Get(T&x){ int c;while(!digit(c=getc()));x=c-'0';while(digit(c=getc()))x=(x<<1)+(x<<3)+c-'0'; } char buf[5000000],*o=buf; inline void putc(char c){*o++=c;} template<typename T>inline void print(T x){ static int stk[100];int top=0; for(;x;x/=10)stk[++top]=x%10;for(int i=top;i>=1;--i)*o++='0'+stk[i]; } inline void Final(){fwrite(buf,1,o-buf,stdout);} } int head[4010],next[2010*2010],end[2010*2010]; inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;} int G[2010][2010],dfn[4010],low[4010],tclock,stk[4010],bel[4010],cnt,top;bool instk[4010]; void dfs(int x){ dfn[x]=low[x]=++tclock;stk[++top]=x,instk[x]=1; for(int j=head[x];j;j=next[j]){ if(!dfn[end[j]])dfs(end[j]),low[x]=std::min(low[x],low[end[j]]); else if(instk[end[j]])low[x]=std::min(low[x],dfn[end[j]]); } if(dfn[x]==low[x]){ ++cnt; while(1){ int i=stk[top--];instk[i]=0; bel[i]=cnt; if(i==x)break; } } } int seq[2010],id; int main(){ int n;Fio::Get(n);register int i,j; int t,x;for(i=1;i<=n;++i){Fio::Get(t);while(t--)Fio::Get(x),G[i][x]=1,addedge(i,n+x);} for(i=1;i<=n;++i)Fio::Get(x),addedge(n+x,i); for(i=1;i<=2*n;++i)if(!dfn[i])dfs(i); for(i=1;i<=n;++i){ for(id=0,j=1;j<=n;++j)if(bel[i]==bel[n+j]&&G[i][j])seq[++id]=j; Fio::print(id); for(j=1;j<=id;++j)Fio::putc(' '),Fio::print(seq[j]); Fio::putc('\n'); //printf("%d",id); //for(j=1;j<=id;++j)printf(" %d",seq[j]); //puts(""); } Fio::Final(); #ifndef ONLINE_JUDGE system("pause"); #endif return 0; }