专题三图论.docx

二分匹配加强连通 HDOJ4685 PrincePrincess题意：20000个点的二分图，冗余边的定义就是如果这条边进入匹配之后，总匹配数无论如何怎么选择都无法达到最大匹配。解法：先求出一次二分匹配，先考虑王子和公主都进入完美匹配的情况，那么对于任意一个王子，对公主建图，从他匹配到的公主连一条边到他剩余喜欢的公 主，含义就是如果这王子不选择之后公主之后还能考虑的其他公主，如果如果这条边不是冗余边，意味着两个公主在一个强连通分量内。现在的情况就是有一些公主没有进入匹配，这样考虑，还是利用上面的是不是在一个强连通分量来判断是不是冗余边，这样子的话就是这个没有匹配的公主连到任意另外一个公主一条边，意味着别人王子匹配到这个公主也可以达到最大匹配。如果一个王子没有进入匹配中，可以保证他喜欢的所有公主都是在匹配中，任意一个他喜欢的公主被别人抛弃之后他都可以进入匹配，连边的话就是从任意其他点连到他喜欢的公主身上，意义就是如果原先匹配这个公主的王子离开后，这个王子就会进入，并且形成回路。这样建图就ok了。还有一点要考虑的就是20000个点的最大匹配，hk和网络流就任君选择了。constintmaxn=1010;intuN,vN;int g[maxn][maxn];int linker[maxn];bool used[maxn];booldfs(int u){for(int v=1;v=vN;v++)if (g[u][v]!used[v]){used[v]=true;if (linker[v]==-1||dfs(linker[v])){linker[v]=u;//给公主搭配的是哪位王子return true;}}return false;}inthungary(){int res=0;Fill(linker,-1);for(int u=1;u=uN;u++){memset(used,false,sizeof(used));if (dfs(u)) res++;}return res;}int lx[maxn];constintmaxm=500100;struct Edge{intto,next;}edge[maxm];int head[maxn],tot;int low[maxn],dfn[maxn],stack[maxn],belong[maxn];intindex,top;intscc;boolinstack[maxn];intnum[maxn];voidaddedge(intu,int v){edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;}voidTarjan(int u){int v;low[u]=dfn[u]=++index;stack[top++]=u;instack[u]=true;for(inti=head[u];i!=-1;i=edge[i].next){v=edge[i].to;if (!dfn[v]){Tarjan(v);if (low[u]low[v]) low[u]=low[v];}else if (instack[v]low[u]dfn[v])low[u]=dfn[v];}if (low[u]==dfn[u]){scc++;do{v=stack[--top];instack[v]=false;belong[v]=scc;num[scc]++;}while(v!=u);}}void solve(int N){Fill(dfn,0);Fill(instack,0);Fill(num,0);index=scc=top=0;for(inti=1;i=N;i++)if (!dfn[i]) Tarjan(i);}voidinit(){tot=0;Fill(head,-1);}int main(){input;intn,m,k,T;cinT;for(int Case=1;Case=T;Case++){scanf(%d%d,n,m);Fill(g,0);int v;for(inti=1;i=n;i++){scanf(%d,k);while(k--){scanf(%d,v);g[i][v]=1;}}uN=n;vN=m;int res=hungary();uN=vN=n+m-res;for(inti=n+1;i=uN;i++)for(int j=1;j=vN;j++)g[i][j]=1;for(inti=1;i=uN;i++)for(int j=m+1;j=vN;j++)g[i][j]=1;hungary();Fill(lx,-1);init();for(inti=1;i=vN;i++)if (linker[i]!=-1)//当前搜索的该公主被王子所搭配lx[linker[i]