POJ1904 King's Quest（完备匹配可行边：强连通分量）

题目大概就是说给一张二分图以及它的一个完备匹配，现在问X部的各个点可以与Y部那些些点匹配，使得X部其余点都能找到完备匹配。

枚举然后匹配，当然不行，会超时。

这题的解法是，在二分图基础上建一个有向图：原二分图中边(x,y)连<x,y>的弧，对于那个已知的匹配中的所有边(x,y)连<y,x>的弧，然后对于X部各个点x如果它到Y部的y点有直接的边且它们在同一个强连通分量，那么x就能和y匹配。

我对这个解法的理解是这样的，类似于匈牙利算法的增广路：

如果x和y就属于给定的那个完备匹配那它们本来就在强连通分量上；
否则，就在原匹配的基础上在构造的有向图上走，看能否找到一条“增广路”（其实不是增广路）去修正，看能否使得x匹配的点改成y——

x走向y，这条边必定不属于原匹配，那么这条边加入匹配集合

y走向x1，这条边必定属于原匹配，那么这条边从匹配集合中删去

x1走向y1，这条边必定不属于原匹配，那么这条边加入匹配集合

…… …… ……

最后如果就存在一个yn走能向x，这条边必定属于原匹配，删去；而删除这条边后，就没有和最开头加入匹配集合的那条(x,y)的边存在公共点的边了，(x,y)就是一个合法的匹配

感觉这解法很巧。而这二分图上的边最大独立集，性质挺多的，感觉也挺难运用这些性质。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 #define MAXN 4444

 #define MAXM 2222*2222

 struct Edge{

     int v,next;

 }edge[MAXM];

 int NE,head[MAXN];

 void addEdge(int u,int v){

     edge[NE].v=v; edge[NE].next=head[u];

     head[u]=NE++;

 }

 int top,stack[MAXN];

 bool instack[MAXN];

 int dn,dfn[MAXN],low[MAXN];

 int bn,belong[MAXN];

 void tarjan(int u){

     dfn[u]=low[u]=++dn;

     stack[++top]=u; instack[u]=;

     for(int i=head[u]; i!=-; i=edge[i].next){

         int 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]){

         int v; ++bn;

         do{

             v=stack[top--];

             instack[v]=;

             belong[v]=bn;

         }while(u!=v);

     }

 }

 int main(){

     int n,a,b;

     while(~scanf("%d",&n)){

         NE=;

         memset(head,-,sizeof(head));

         for(int i=; i<=n; ++i){

             scanf("%d",&a);

             while(a--){

                 scanf("%d",&b);

                 addEdge(i,b+n);

             }

         }

         for(int i=; i<=n; ++i){

             scanf("%d",&a);

             addEdge(a+n,i);

         }

         top=dn=bn=;

         memset(dfn,,sizeof(dfn));

         memset(instack,,sizeof(instack));

         for(int i=; i<=*n; ++i){

             if(dfn[i]==){

                 tarjan(i);

             }

         }

         for(int u=; u<=n; ++u){

             int cnt=;

             bool vis[MAXN]={};

             for(int i=head[u]; i!=-; i=edge[i].next){

                 int v=edge[i].v;

                 if(belong[u]==belong[v]){

                     ++cnt;

                     vis[v-n]=;

                 }

             }

             printf("%d",cnt);

             for(int i=; i<=n; ++i){

                 if(vis[i]){

                     printf(" %d",i);

                 }

             }

             putchar('\n');

         }

     }

     return ;

 }

巴特西

POJ1904 King's Quest（完备匹配可行边：强连通分量）

最新文章

热门文章