題意:
? ? ? 給你n個王子和m個公主,每個王子可以和自己喜歡的公主結婚,問你在不影響最大匹配的前提下每個王子都可以去哪些公主.


思路:

? ? ? 所有王子向他喜歡的公主連一條邊,然后匹配一遍,之后再每個匹配的公主連一條指向娶她的王子一條邊,然后對于那些光棍王子和單身公主們,其實他們可以和任意他們喜歡的人匹配,因為可以讓自己幸福,然后拆散一對別人已經匹配好的,雖然不道德,但是仍然滿足總的最大匹配數不變,所以對于每一個光棍男我們就給他虛擬出一個女朋友,所有人都喜歡這個女的,但是這個女的只喜歡并且和該光棍男匹配,女的也類似這樣弄,最后每個人都有匹配的對象了,此時我們只要跑一遍強連通,同一個強連通分量里的男和女可以隨意匹配..

#include<stdio.h> #include<string.h> #include<algorithm> #include<stack> #include<map>#define N_node 5000 #define N_edge 600000 using namespace std;typedef struct {int to ,next; }STAR;STAR E[N_edge] ,_E[N_edge] ,__E[N_edge]; map<int ,map<int ,int> >mk_map; int list[N_node] ,_list[N_node] ,tot , _tot; int Belong[N_node] ,cout; int mk_dfs[N_node] ,mk_gx[N_node]; int mk_M[550] ,mk_G[550]; stack<int>st; void add(int a, int b) {E[++tot].to = b;E[tot].next = list[a];list[a] = tot;_E[++_tot].to = a;_E[_tot].next = _list[b];_list[b] = _tot; }int DFS_XYL(int s) {for(int k = list[s] ;k ;k = E[k].next){int to = E[k].to;if(mk_dfs[to]) continue;mk_dfs[to] = 1;if(mk_gx[to] == -1 || DFS_XYL(mk_gx[to])){mk_gx[to] = s;return 1;}}return 0; }void DFS_1(int s) {mk_dfs[s] = 1;for(int k = list[s] ;k ;k = E[k].next){int to = E[k].to;if(mk_dfs[to]) continue;DFS_1(to);}st.push(s); }void DFS_2(int s) {mk_dfs[s] = 1;Belong[s] = cout;for(int k = _list[s] ;k ;k = _E[k].next){int to = _E[k].to;if(mk_dfs[to]) continue;DFS_2(to);} }void solve(int cas) {int n ,m ,i ,j;int a ,b ,c;scanf("%d %d" ,&n ,&m);memset(list ,0 ,sizeof(list));memset(_list ,0 ,sizeof(_list));tot = _tot = 1;mk_map.clear();for(i = 1 ;i <= n ;i ++){scanf("%d" ,&c);while(c--){scanf("%d" ,&a);add(i ,a + n);mk_map[i][a] = 1;}}memset(mk_gx ,255 ,sizeof(mk_gx));int sum = 0;for(i = 1 ;i <= n ;i ++){memset(mk_dfs ,0 ,sizeof(mk_dfs));mk_M[i] = DFS_XYL(i);sum += mk_M[i];}for(i = 1 ;i <= m ;i ++){if(mk_gx[i + n] == -1) mk_G[i] = 0;else{mk_G[i] = 1;add(i + n ,mk_gx[i + n]);}}int nowid = n + m;for(i = 1 ;i <= n ;i ++){if(mk_M[i]) continue;nowid ++;for(j = 1 ;j <= n ;j ++)add(j ,nowid);add(nowid ,i);}for(i = 1 ;i <= m ;i ++){if(mk_G[i]) continue;nowid ++;for(j = 1 ;j <= m ;j ++)add(nowid ,j + n);add(i + n ,nowid);}memset(mk_dfs ,0 ,sizeof(mk_dfs));while(!st.empty()) st.pop();for(i = 1 ;i <= nowid ;i ++){if(mk_dfs[i]) continue;DFS_1(i);}cout = 0;memset(mk_dfs ,0 ,sizeof(mk_dfs));while(!st.empty()){int to = st.top();st.pop();if(mk_dfs[to]) continue;cout ++;DFS_2(to);} printf("Case #%d:\n" ,cas);int tmp[550];for(i = 1 ;i <= n ;i ++){int tt = 0;for(int k = list[i] ;k ;k = E[k].next){int to = E[k].to;if(mk_map[i][to - n] && Belong[i] == Belong[to])tmp[++tt] = to - n;}sort(tmp + 1 ,tmp + tt + 1); printf("%d" ,tt);for(int k = 1 ;k <= tt ;k ++)printf(" %d" ,tmp[k]);printf("\n");} }int main () {int cas = 1 ,t;scanf("%d" ,&t);while(t--){solve(cas++);}return 0; }

總結

以上是生活随笔為你收集整理的hdu4685 最大匹配可能性的全部內容，希望文章能夠幫你解決所遇到的問題。

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