傳送門

題意：每個兒子都喜歡許多女孩，問每個渣男兒子最多有幾個可以選擇備胎。他爹也挺渣。。

猛地一看，哇二分匹配，但是想了想輸入輸出都能卡時間的題目，循環(huán)暴力二分匹配必T無疑，在做強連通模塊的題所以想了好久也不知道怎么轉化。看了大佬的博客，解釋的特別好。

首先題目是給了一個完備匹配了的，思想如下：

設一個渣男為m1，一個小女孩為g1，在所給的完備匹配中m1<->g1，他們倆是肯定成立的。

然后渣男m1又喜歡的女孩g2，所以注意此時的圖為

g2又去找他的完備匹配的是誰，不管中間多復雜，如果想要成立一個與原來的匹配不同的選擇，必定最后有一條邊是回到g1的，因為之前選g1的渣男m1他去選g2,所以此時顯然就出現(xiàn)了一個環(huán)，既然是環(huán)，即是強連通，即每一個渣男可以選擇強連通分量里邊每一個girl，所以此時做法就是男孩向女孩引邊，再從女孩向男孩引邊，tanjar，最后看每一個男孩對應的女孩是不是一個強連通分量即可。

ac代碼：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define me(a,b) memset(a,b,sizeof(a))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
typedef long long ll;
using namespace std;
const int maxn=2e3+5;
const int M=2e5+5;
int low[2*maxn],dfn[2*maxn],Stack[2*maxn],inStack[2*maxn],belong[2*maxn],head[2*maxn];
int sign,top,cnt,t,n;
vector<int>ans;
struct node
{int to,p;
}edge[maxn+M];
void init()
{sign=top=cnt=t=0;for(int i=1;i<=2*n;i++){low[i]=dfn[i]=inStack[i]=0;belong[i]=head[i]=-1;}
}
void add(int u,int v)
{edge[sign]=node{v,head[u]};head[u]=sign++;
}
void tanjar(int u)
{low[u]=dfn[u]=++t;Stack[++top]=u;inStack[u]=1;for(int i=head[u];i!=-1;i=edge[i].p){int v=edge[i].to;if(!dfn[v]){tanjar(v);low[u]=min(low[u],low[v]);}else if(inStack[v])low[u]=min(low[u],dfn[v]);}int x;if(low[u]==dfn[u]){cnt++;do{x=Stack[top--];inStack[x]=0;belong[x]=cnt;}while(u!=x);}
}
int main()
{int num,x;while(scanf("%d",&n)!=EOF){init();for(int i=1;i<=n;i++){scanf("%d",&num);while(num--){scanf("%d",&x);add(i,x+n);}}for(int i=1;i<=n;i++){scanf("%d",&x);add(x+n,i);}for(int i=1;i<=n;i++){if(!dfn[i])tanjar(i);}for(int i=1;i<=n;i++){ans.clear();for(int j=head[i];j!=-1;j=edge[j].p){int v=edge[j].to;if(belong[i]==belong[v])ans.push_back(v-n);}sort(ans.begin(),ans.end());int l=ans.size();printf("%d",l);for(int k=0;k<l;k++)printf(" %d",ans[k]);printf("\n");}}return 0;
}

?

總結

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

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