这个题就是建图费点劲,别的和我上一篇博客一样
然后,参考思路请戳这里http://www.cnblogs.com/wally/archive/2013/09/12/3317883.html
补充:这个思路是对的,然后请注意虚拟只和现实的连接,虚拟的不会和虚拟连接
这样可以保证如果在同一连通分量内,还会形成完美匹配,而且原最大匹配也不会有影响
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <string> #include <stack> #include <vector> #include <map> #include <queue> #include <algorithm> #include <utility> using namespace std; typedef long long LL; const int N=2e3+5; const int INF=0x3f3f3f3f; struct Edge{ int v,next; }edge[N*N]; int head[N],tot,n,m; void add(int u,int v){ edge[tot].v=v; edge[tot].next=head[u]; head[u]=tot++; } bool vis[N]; int match[N]; bool dfs(int u){ for(int i=head[u];~i;i=edge[i].next){ int v=edge[i].v; if(vis[v])continue; vis[v]=true; if(match[v]==-1||dfs(match[v])){ match[u]=v; match[v]=u; return true; } } return false; } stack<int>s; bool instack[N],mp[N/2][N/2]; int dfn[N],low[N],clk,cnt,bel[N]; void targin(int u){ dfn[u]=low[u]=++clk; instack[u]=true;s.push(u); for(int i=head[u];~i;i=edge[i].next){ int v=edge[i].v; if(!dfn[v]){ targin(v); low[u]=min(low[u],low[v]); } else if(instack[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]){ ++cnt;int k; do{ k=s.top(); s.pop(); instack[k]=false; bel[k]=cnt; }while(k!=u); } } vector<int>g; int main() { int T,cas=0; scanf("%d",&T); while(T--){ printf("Case #%d: ",++cas); scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); memset(mp,0,sizeof(mp)); clk=cnt=tot=0; for(int i=1;i<=n;++i){ int k;scanf("%d",&k); for(int j=0;j<k;++j){ int u;scanf("%d",&u); add(i,u+n); mp[i][u+n]=true; } } int tol=0; memset(match,-1,sizeof(match)); for(int i=1;i<=n;++i){ memset(vis,0,sizeof(vis)); if(dfs(i))++tol; } for(int i=1;i<=m-tol;++i){ int u=i+1000; for(int j=n+1;j<=n+m;++j) add(u,j); } for(int i=1;i<=n-tol;++i){ int v=1000+m-tol+i; for(int j=1;j<=n;++j) add(j,v); } int cur=1000; for(int i=n+1;i<=n+m;++i){ if(match[i]!=-1)add(i,match[i]); else add(i,++cur); } cur=1000+m-tol; for(int i=1;i<=n;++i){ if(match[i]!=-1)continue; else add(++cur,i); } memset(instack,0,sizeof(instack)); memset(dfn,0,sizeof(dfn)); for(int i=1;i<=n;++i) if(!dfn[i])targin(i); for(int i=1001;i<=1000+m-tol;++i) if(!dfn[i])targin(i); for(int i=1;i<=n;++i){ g.clear(); for(int j=n+1;j<=n+m;++j){ if(!mp[i][j]||bel[i]!=bel[j])continue; g.push_back(j-n); } printf("%d",g.size()); for(int j=0;j<g.size();++j) printf(" %d",g[j]); printf(" "); } } return 0; }