題目鏈接：點(diǎn)擊查看

題目大意：給出n個(gè)王子和m個(gè)公主，每個(gè)王子都有喜歡的公主，題目需要我們?cè)诒M可能多的王子可以匹配到喜歡的公主的情況下，求出每個(gè)王子所能娶的所有公主，必須保證王子娶了其中任何一個(gè)之后，其他的王子也都能娶到自己喜歡的公主

題目分析：poj1904的加強(qiáng)版，之前那個(gè)題是n個(gè)王子和n個(gè)公主，并且初始時(shí)就已經(jīng)給出了完備匹配，但是這個(gè)題目需要讓我們自己求出完備匹配，然后剩下的就和之前那個(gè)題目一樣了，因?yàn)檫@個(gè)題目的數(shù)據(jù)比較小，所以直接用鄰接矩陣來儲(chǔ)存的邊

至于如何求出二分圖完備匹配，我們可以引入一個(gè)虛擬點(diǎn)的概念，首先建好邊后跑一遍匈牙利，求出二分圖最大匹配為cnt，這時(shí)肯定還有n-cnt個(gè)王子和m-cnt個(gè)公主沒有匹配，我們?cè)谕踝舆@邊加入m-cnt個(gè)虛擬點(diǎn)和所有的公主連邊，在公主這邊加入n-cnt個(gè)虛擬點(diǎn)和所有的王子連邊，隨后在第一次匹配后的基礎(chǔ)上再跑一次最大匹配，這一次匹配后的答案一定就是完備匹配了，也就是max(n,m)，我們主要需要的是匹配的結(jié)果，現(xiàn)在有了匹配結(jié)果就可以按照poj1904的步驟繼續(xù)下去了，強(qiáng)連通縮點(diǎn)后直接找答案就好了，因?yàn)樵谝粋€(gè)強(qiáng)連通集合中的點(diǎn)都是可以互換的，所以不影響最大匹配的結(jié)果

這里為了提高一點(diǎn)匈牙利匹配的效率，即可以在加入虛擬點(diǎn)后在第一次匹配的基礎(chǔ)上繼續(xù)匹配，我對(duì)內(nèi)部實(shí)現(xiàn)稍作修改，新增了book數(shù)組用來記錄哪些王子已經(jīng)匹配成功，第二次的時(shí)候就不對(duì)其進(jìn)行處理了

代碼：

#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=2e3+100;const int M=N*N;struct Egde {int to,next; }edge1[M];int head1[N],low[N],dfn[N],c[N],Stack[N],match[N],num,cnt,cnt1,dcc,n,m,nn,mm,top;bool ins[N],maze[N][N],vis[N],book[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);} }bool dfs(int x) {for(int i=1;i<=mm;i++){if(!vis[i]&&maze[x][i]){vis[i]=true;if(!match[i]||dfs(match[i])){book[x]=true;match[i]=x;return true;}} }return false; }int hungry() {int ans=0;for(int i=1;i<=nn;i++){memset(vis,false,sizeof(vis));if(!book[i]&&dfs(i))ans++;}return ans; }void solve() {for(int i=1;i<=n;i++)//縮點(diǎn) 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));memset(maze,false,sizeof(maze));memset(match,0,sizeof(match));memset(book,false,sizeof(book)); }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int w;cin>>w;int kase=0;while(w--){init();scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){int num;scanf("%d",&num);while(num--){int to;scanf("%d",&to);maze[i][to]=true;}}nn=n,mm=m;int temp=hungry();nn=mm=n+m-temp;for(int u=n+1;u<=nn;u++)for(int v=1;v<=m;v++)maze[u][v]=true;for(int u=1;u<=n;u++)for(int v=m+1;v<=mm;v++)maze[u][v]=true;hungry();for(int u=1;u<=nn;u++)for(int v=1;v<=mm;v++)if(maze[u][v])addedge1(u,v+nn);for(int v=1;v<=mm;v++)addedge1(v+nn,match[v]);solve();printf("Case #%d:\n",++kase);for(int u=1;u<=n;u++){vector<int>ans;for(int v=1;v<=m;v++)if(maze[u][v]&&c[u]==c[v+nn])ans.push_back(v);sort(ans.begin(),ans.end());printf("%d",ans.size());for(int i=0;i<ans.size();i++)printf(" %d",ans[i]);putchar('\n');}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 4685 Prince and Princess(强连通缩点+二分图完备匹配)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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