题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4685
题意：n个王子和m个公主，王子只能和他喜欢的公主结婚，公主可以和所有的王子结婚，输出所有王子可能的结婚对象，
必须保证王子与任意这些对象中的一个结婚，都不会影响到剩余的王子的配对数，也就是不能让剩余的王子中突然有一个人没婚可结了。
分析：这题是poj 1904的加强版，poj 1904的王子和公主数是相等的，这里可以不等，且poj 1904给出了一个初始完美匹配，但是这题就要自己求。
所以只要求出完美匹配之后，就和poj 1904的做法就完全相同了，这里就不在赘述了，可以参考：http://www.cnblogs.com/frog112111/p/3384261.html
那么怎么求出完美匹配呢？一开始我用多重匹配的匈牙利算法来做，但是怎么做都不对.......看了题解才恍然大悟=_=
先说几个坑，这题有点奇怪，就是所有王子都可以争着和同一个公主结婚，只要该王子喜欢该公主，感觉公主有点悲哀呀........
比如：2 2
1 1
1 1
输出的答案是：1 1 而不是 1 1
1 1 0
这里就是和poj 1904有点不一样的地方，坑了我好久.........
求完美匹配：
先对原图用匈牙利算法做一遍二分图匹配，但是还有可能剩余一些人还没匹配，只要虚拟出一些节点来匹配剩余的点就行了
假设王子有剩下的，那么每个剩下的王子就连一个虚拟的公主，这个公主被所有的王子都喜欢。
假设公主有剩下的，那么每个剩下的公主就连一个虚拟的王子，这个王子喜欢所有的公主
这样就构成完美匹配了，接下来就是和poj 1904一样了。
注意：虽然n和m才500，但是数组要开到2000才能过，可能是剩余太多顶点没匹配，所以要虚拟出比较多的顶点吧，我只开到1500，wa到死=_=
还有就是一些细节没处理好也贡献了好多wa，做了一天.........快奔溃了，最后参考别人的代码改来改去才AC，好艰辛，不过最终能过也算安慰了
果然想问题还是不够周全，不够细心
大三了都，哎，弱成一坨翔了~
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
const int M=+;
struct EDGE{
int v,next;
}edge[M];
int first[N],low[N],dfn[N],sta[M],belong[N];
int ans[N],match[N],flag[N];
bool instack[N],vis[N];
int n,m,g,cnt,top,scc,maxn;
int Scan() //输入外挂
{
int res=,ch,flag=;
if((ch=getchar())=='-')
flag=;
else if(ch>=''&&ch<='')
res=ch-'';
while((ch=getchar())>=''&&ch<='')
res=res*+ch-'';
return flag?-res:res;
}
void Out(int a) //输出外挂
{
if(a>)
Out(a/);
putchar(a%+'');
}
void AddEdge(int u,int v)
{
edge[g].v=v;
edge[g].next=first[u];
first[u]=g++;
}
int min(int a,int b)
{
return a<b?a:b;
}
int max(int a,int b)
{
return a>b?a:b;
}
void init()
{
g=cnt=top=scc=;
memset(first,-,sizeof(first));
memset(dfn,,sizeof(dfn));
memset(instack,false,sizeof(instack));
memset(flag,,sizeof(flag));
//scanf("%d%d",&n,&m);
n=Scan();
m=Scan();
maxn=max(n,m); //王子和公主数可能不同，为了建图方便去较大者，王子编号1--maxn,公主编号maxn+1--2*maxn
}
bool dfs(int u)
{
int i,v;
for(i=first[u];i!=-;i=edge[i].next)
{
v=edge[i].v;
if(!vis[v])
{
vis[v]=true;
if(match[v]==||dfs(match[v]))
{
match[v]=u;
flag[u]=v;
return true;
}
}
}
return false;
}
void xiong() //二分匹配
{
int i;
memset(match,,sizeof(match));
for(i=;i<=maxn;i++)
{
memset(vis,false,sizeof(vis));
dfs(i);
}
}
void Tarjan(int u) //求强连通分量
{
int i,v;
low[u]=dfn[u]=++cnt;
sta[++top]=u;
instack[u]=true;
for(i=first[u];i!=-;i=edge[i].next)
{
v=edge[i].v;
if(!dfn[v])
{
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(instack[v])
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
scc++;
while()
{
v=sta[top--];
instack[v]=false;
belong[v]=scc;
if(u==v)
break;
}
}
}
void build()
{
int i,k,v,j;
for(i=;i<=n;i++)
{
// scanf("%d",&k);
k=Scan();
while(k--)
{
// scanf("%d",&v);
v=Scan();
AddEdge(i,v+maxn); //王子和喜欢的公主之间连边
}
} xiong(); //做一次二分匹配 int all=*maxn;
for(i=;i<=maxn;i++) //为剩余王子匹配虚拟公主
{
if(!flag[i])
{
all++;
for(j=;j<=maxn;j++) //所有王子都喜欢该虚拟公主
AddEdge(j,all);
match[all]=i;
flag[i]=all;
}
} for(i=maxn+;i<=*maxn;i++) //为剩余公主匹配虚拟王子
{
if(!match[i])
{
all++;
for(j=maxn+;j<=*maxn;j++) //该虚拟王子喜欢所有公主
AddEdge(all,j);
flag[all]=i;
match[i]=all;
}
}
for(i=;i<=all;i++) //所有与王子匹配的公主建一条边连向王子
{
if(flag[i])
AddEdge(flag[i],i);
}
}
void solve()
{
int i,u,v;
for(i=;i<=maxn;i++) //求强连通分量
if(!dfn[i])
Tarjan(i); for(u=;u<=n;u++) //枚举所有王子
{
int count=;
for(i=first[u];i!=-;i=edge[i].next)
{
v=edge[i].v;
if(belong[u]==belong[v]) //王子与公主同在一个强连通分量
{
if(v-maxn>m)
continue;
ans[count++]=v-maxn;
}
}
sort(ans,ans+count);
// printf("%d",count);
Out(count);
for(i=;i<count;i++) //输出
{
//printf(" %d",ans[i]);
putchar(' ');
Out(ans[i]);
}
// printf("\n");
putchar('\n');
}
}
int main()
{
int t,cas;;
// scanf("%d",&t);
t=Scan();
for(cas=;cas<=t;cas++)
{
init();
build();
printf("Case #%d:\n",cas);
solve();
}
return ;
}