題目鏈接：點擊查看

題目大意：給出n個王子和n個公主，每個王子都有喜歡的公主，每個王子初始時都娶到了一位喜歡的公主，題目需要我們求出每個王子所能娶的所有公主，必須保證王子娶了其中任何一個之后，其他的王子也都能娶到自己喜歡的公主

題目分析：首先對于初始時，已經(jīng)存在了二分圖的完備匹配，也就是每個王子都能和喜歡的公主結(jié)婚，不過當(dāng)前只有一個答案，但實際上答案可能不止于此，所以我們需要強連通縮點，先解釋一下為什么需要強連通縮點吧，因為若一個王子想要去娶另一個公主，那么必須保證原先公主所配對的王子也可以再去找到另一個公主，換句話說，強連通縮點后的每個集合中的王子數(shù)必須等于公主數(shù)，這樣整個強連通集合中的點就可以互相配對了，因為都強連通了嘛，所以直接套模板就好了

需要注意的是這個題目的輸入和輸出非常大，正常scanf和printf的話都跑了10秒，用快讀和快輸能快上十倍，偶爾用一下加速外掛感覺也是蠻不錯的

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=4e3+100;const int M=2e5+N;inline int read() {int w=1,q=0;char ch=' ';while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();if(ch=='-')w=-1,ch=getchar();while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();return w*q; }inline int write(int x) {if(x<0){putchar('-');x=~(x-1);}int s[20],top=0;while(x){s[++top]=x%10;x/=10;}if(!top)s[++top]=0;while(top)putchar(s[top--]+'0'); }struct Egde {int to,next; }edge1[M];int head1[N],low[N],dfn[N],c[N],Stack[N],num,cnt,cnt1,dcc,n,m,top;bool ins[N];vector<int>scc[N];void addedge1(int u,int v) {edge1[cnt1].to=v;edge1[cnt1].next=head1[u];head1[u]=cnt1++; }void tarjan(int u) {dfn[u]=low[u]=++num;Stack[++top]=u;ins[u]=true;for(int i=head1[u];i!=-1;i=edge1[i].next){int v=edge1[i].to;if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(ins[v])low[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u]){cnt++;int v;do{v=Stack[top--];ins[v]=false;c[v]=cnt;scc[cnt].push_back(v);}while(u!=v);} }void solve() {for(int i=1;i<=n;i++)//縮點 if(!dfn[i])tarjan(i); }void init() {for(int i=0;i<N;i++)scc[i].clear();top=cnt=num=dcc=0;memset(head1,-1,sizeof(head1));memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));memset(c,0,sizeof(c));memset(ins,false,sizeof(ins)); }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);while(scanf("%d",&n)!=EOF){init();for(int i=1;i<=n;i++){int num;num=read();while(num--){int to;to=read();addedge1(i,to+n);}}for(int i=1;i<=n;i++){int to;to=read();addedge1(to+n,i);}solve();for(int u=1;u<=n;u++){vector<int>ans;for(int i=head1[u];i!=-1;i=edge1[i].next){int v=edge1[i].to;if(c[u]==c[v])ans.push_back(v-n);}sort(ans.begin(),ans.end());write(ans.size());for(int i=0;i<ans.size();i++){putchar(' ');write(ans[i]);}putchar('\n');}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的POJ - 1904 King's Quest(强连通缩点)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。