hdu4685:http://acm.hdu.edu.cn/showproblem.php?pid=4685
题意：有n个王子和m个公主，每个王子都会喜欢若干个公主，也就是王子只跟自己喜欢的公主结婚公主就比较悲惨， 跟谁结婚都行，然后输出王子可能的结婚对象。
题解：这一题看了题解之后，也还是只知道是怎么做的，至于为什么那么做还是不懂啊。
解题步奏：首先让王子和喜欢的人之间建立一条边，然后，求一个最大匹配res，然后左边王子加入m-res个虚拟王子，右边加入n-res虚拟公主，所以新加入的王子喜欢所有的公主，所有加入的公主被所有的王子喜欢，然后再跑最大匹配。如果，对于第i个王子，把他喜欢的公主，然后建立一条边，然后缩点，在同一个连通块中的是可以交换的(这里不是很理解)。然后输出。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=;
const int M=;
const int INF=0xffffffff;
int n,m,u,cnt,dep,top,atype,newn,newm;
int dfn[N],low[N],vis[N],head[N],st[N],belong[N],lx[N],cy[N];
bool visit[N],g[N][N];
vector<int>ans;
int path(int u){
for(int i=;i<=newm;i++){
if(!visit[i]&&g[u][i]){
visit[i]=;
if(cy[i]==-||path(cy[i])){
cy[i]=u;
return ;
}
}
}
return ;
}
int maxmatch(){
memset(cy,-,sizeof(cy));
int res=;
for(int i=;i<=newn;i++){
memset(visit,,sizeof(visit));
res+=path(i);
}
return res;
}
struct Edge{
int to,next;
} edge[M];
void init(){
cnt=dep=top=atype=;
memset(head,-,sizeof(head));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(vis,,sizeof(vis));
memset(belong,,sizeof(belong));
memset(g,,sizeof(g));
}
void addedge(int u,int v){
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
} void Tarjan(int u){
dfn[u]=low[u]=++dep;
st[top++]=u;
vis[u]=;
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].to;
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v]){
low[u]=min(low[u],dfn[v]);
}
}
int j;
if(dfn[u]==low[u]){
atype++;
do{
j=st[--top];
belong[j]=atype;
vis[j]=;
}
while(u!=j);
}
}
int cas;
int main(){
scanf("%d",&cas);
int tt=;
while(cas--){
scanf("%d%d",&n,&m);
init();
for(int i=;i<=n;i++){
int temp;
scanf("%d",&temp);
for(int j=;j<=temp;j++){
scanf("%d",&u);
g[i][u]=;
}
}
newn=n;newm=m;
int ans1=maxmatch();
newn=n+m-ans1;
newm=n+m-ans1;
for(int i=n+;i<=newn;i++){
for(int j=;j<=newm;j++)
g[i][j]=;
}
for(int i=;i<=newn;i++){
for(int j=+m;j<=newm;j++)
g[i][j]=;
}
maxmatch();
memset(lx,-,sizeof(lx));
for(int i=;i<=newm;i++){
if(cy[i]!=-)
lx[cy[i]]=i;
}
for(int i=;i<=newn;i++){
for(int j=;j<=newm;j++){
if(g[i][j]&&j!=lx[i])
addedge(lx[i],j);
}
}
for(int i=;i<=newm;i++)
if(!dfn[i])
Tarjan(i);
printf("Case #%d:\n",tt++);
for(int i=;i<=n;i++){
ans.clear();
for(int j = ; j <= m;j++)
if(g[i][j] && belong[j] == belong[lx[i]])
ans.push_back(j);
int sz = ans.size();
printf("%d",sz);
for(int i = ;i < sz;i++)
printf(" %d",ans[i]);
printf("\n");
}
}
}