Prince and Princess

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 1847    Accepted Submission(s): 543 Problem Description There are n princes and m princesses. Princess can marry any prince. But prince can only marry the princess they DO love. For all princes,give all the princesses that they love. So, there is a maximum number of pairs of prince and princess that can marry. Now for each prince, your task is to output all the princesses he can marry. Of course if a prince wants to marry one of those princesses,the maximum number of marriage pairs of the rest princes and princesses cannot change.   Input The first line of the input contains an integer T(T<=25) which means the number of test cases. For each test case, the first line contains two integers n and m (1<=n,m<=500), means the number of prince and princess. Then n lines for each prince contain the list of the princess he loves. Each line starts with a integer k _i(0<=k _i<=m), and then k _i different integers, ranging from 1 to m denoting the princesses.   Output For each test case, first output "Case #x:" in a line, where x indicates the case number between 1 and T. Then output n lines. For each prince, first print li, the number of different princess he can marry so that the rest princes and princesses can still get the maximum marriage number. After that print li different integers denoting those princesses,in ascending order.   Sample Input 2 4 4 2 1 2 2 1 2 2 2 3 2 3 4 1 2 2 1 2   Sample Output Case #1: 2 1 2 2 1 2 1 3 1 4 Case #2: 2 1 2   Source 2013 Multi-University Training Contest 8    Recommend zhuyuanchen520

题目大意：

    有N个王子,M个公主，每个王子都有一些喜欢的公主，问每个王子可以选择的公主，使得总的匹配对数最大。

解题思路：

    这题和POJ 1904很像，可以说是那道题的升级版，唯一的变化就是没有了题目给出的初始匹配，并且王子数和公主数可以不一样。（下面的分析是基于POJ 1904的）

    那么我们就可以在POJ 1904的基础上写这道题。少了初始匹配，我们可以自己跑一边二分图最大匹配的到一个初始匹配。由于题目保证一定是完美匹配，所以可能会有王子和公主在初始匹配中没有对象。我们可以发现，如果没有对象的人和满足条件的人匹配，他匹配的人原来匹配的对象单身，是不影响匹配数的，所以没有对象的人可以人任意的人交换，只要最后统计的时候去掉不喜欢的就可以了。所以为了能够让他能与其他人交换，就可给ta设置一个虚拟对象，让ta与虚拟对象匹配，然后让虚拟对象喜欢其它所有异性或被所有异性喜欢。之后就可以像POJ 1904一样强连通分量分解，然后一个联通块内喜欢的人就是答案。

AC代码：

#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <ctime> #include <vector> #include <queue> #include <stack> #include <deque> #include <string> #include <map> using namespace std; #define INF 0x3f3f3f3f #define LL long long #define fi first #define se second #define mem(a,b) memset((a),(b),sizeof(a)) const int MAXN=500+3; const int MAXV=MAXN*4; vector<int> G0[MAXV],G1[MAXV];//喜欢关系，按照分析建的图 int N,M,V; int match_x[MAXV],match_y[MAXV];//顶点匹配对象 int dis,dis_x[MAXV],dis_y[MAXV];//距离（用于多路增广） bool used[MAXV]; int dfn[MAXV],low[MAXV],vis[MAXV],tmpdfn,scc,belong[MAXV]; stack<int> st; bool searchP()//标记距离（用于多路增广） { queue<int> que; dis=INF; mem(dis_x,-1); mem(dis_y,-1); for(int i=0;i<N;++i) if(match_x[i]==-1) { que.push(i); dis_x[i]=0; } while(!que.empty()) { int u=que.front(); que.pop(); if(dis_x[u]>dis) break; for(int i=0;i<G0[u].size();++i) { int v=G0[u][i]; if(dis_y[v]==-1) { dis_y[v]=dis_x[u]+1; if(match_y[v]==-1) dis=dis_y[v]; else { dis_x[match_y[v]]=dis_y[v]+1; que.push(match_y[v]); } } } } return dis!=INF; } bool dfs(int u)//dfs增广 { for(int i=0;i<G0[u].size();++i) { int v=G0[u][i]; if(!used[v]&&dis_y[v]==dis_x[u]+1) { used[v]=true; if(match_y[v]!=-1&&dis_y[v]==dis) continue; if(match_y[v]==-1||dfs(match_y[v])) { match_y[v]=u; match_x[u]=v; return true; } } } return false; } int hopcroft_carp()//二分图匹配 { int res=0; mem(match_x,-1); mem(match_y,-1); while(searchP()) { mem(used,0); for(int i=0;i<N;++i) if(match_x[i]==-1&&dfs(i)) ++res; } return res; } void init()//初始化 { for(int i=0;i<N;++i) G0[i].clear(); for(int i=0;i<V*2;++i) { G1[i].clear(); vis[i]=0; } tmpdfn=scc=0; } void tarjan(int u)//建的图一定不会有重边，所以不用处理重边 { vis[u]=1; dfn[u]=low[u]=tmpdfn++; st.push(u); for(int i=0;i<G1[u].size();++i) { int v=G1[u][i]; if(vis[v]==0) { tarjan(v); low[u]=min(low[u],low[v]); } else if(vis[v]==1) low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]) { int v; do{ v=st.top(); st.pop(); belong[v]=scc; vis[v]=2; }while(v!=u); ++scc; } } int main() { int T_T; scanf("%d",&T_T); for(int cas=1;cas<=T_T;++cas) { scanf("%d%d",&N,&M); int Vx=max(N,M); V=2*Vx; init(); for(int u=0;u<N;++u) { int num; scanf("%d",&num); for(int i=0;i<num;++i) { int v; scanf("%d",&v); --v; G0[u].push_back(v); } } hopcroft_carp(); // 0 ~ Vx-1 王子 // Vx ~ 2*Vx-1 公主 // 2*Vx ~ ... 虚拟的人 int now=V; for(int u=0;u<N;++u) { for(int i=0;i<G0[u].size();++i) { int v=G0[u][i]; G1[u].push_back(v+Vx); } if(match_x[u]!=-1) G1[match_x[u]+Vx].push_back(u); else//有没有匹配的王子 { G1[now].push_back(u); for(int i=0;i<N;++i) G1[i].push_back(now); ++now; } } for(int u=0;u<M;++u) { if(match_y[u]==-1)//有没有匹配的公主 { G1[u+Vx].push_back(now); for(int i=Vx;i<Vx+M;++i) G1[now].push_back(i); ++now; } } for(int i=0;i<V;++i) if(vis[i]==0) tarjan(i); printf("Case #%d:\n",cas); int save[MAXN]; for(int u=0;u<N;++u) { int cnt=0; for(int i=0;i<G0[u].size();++i)//只有本来就喜欢的，在同一个强连通分量的人才算 { int v=G0[u][i]; if(belong[u]==belong[v+Vx]) save[cnt++]=v; } printf("%d",cnt); sort(save,save+cnt); for(int i=0;i<cnt;++i) printf(" %d",save[i]+1); putchar('\n'); } } return 0; }