首页 > 代码库 > Prince and Princess

Prince and Princess

2024-07-18 03:34:34   211人阅读

hdu4685:http://acm.hdu.edu.cn/showproblem.php?pid=4685

题意：有n个王子和m个公主，每个王子都会喜欢若干个公主，也就是王子只跟自己喜欢的公主结婚公主就比较悲惨， 跟谁结婚都行，然后输出王子可能的结婚对象。

题解：这一题看了题解之后，也还是只知道是怎么做的，至于为什么那么做还是不懂啊。

解题步奏：首先让王子和喜欢的人之间建立一条边，然后，求一个最大匹配res，然后左边王子加入m-res个虚拟王子，右边加入n-res虚拟公主，所以新加入的王子喜欢所有的公主，所有加入的公主被所有的王子喜欢，然后再跑最大匹配。如果，对于第i个王子，把他喜欢的公主，然后建立一条边，然后缩点，在同一个连通块中的是可以交换的(这里不是很理解)。然后输出。

  1 #include<iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 #include<vector>  6 using namespace std;  7 const int N=1002;  8 const int M=400010;  9 const int INF=0xffffffff; 10 int  n,m,u,cnt,dep,top,atype,newn,newm; 11 int  dfn[N],low[N],vis[N],head[N],st[N],belong[N],lx[N],cy[N]; 12 bool visit[N],g[N][N]; 13 vector<int>ans; 14 int path(int u){ 15      for(int i=1;i<=newm;i++){ 16         if(!visit[i]&&g[u][i]){ 17             visit[i]=1; 18         if(cy[i]==-1||path(cy[i])){ 19             cy[i]=u; 20             return 1; 21         } 22        } 23      } 24    return 0; 25 } 26 int maxmatch(){ 27     memset(cy,-1,sizeof(cy)); 28     int res=0; 29     for(int i=1;i<=newn;i++){ 30     memset(visit,0,sizeof(visit)); 31         res+=path(i); 32     } 33     return res; 34 } 35 struct Edge{ 36     int to,next; 37 } edge[M]; 38 void init(){ 39       cnt=dep=top=atype=0; 40     memset(head,-1,sizeof(head)); 41     memset(dfn,0,sizeof(dfn)); 42     memset(low,0,sizeof(low)); 43     memset(vis,0,sizeof(vis)); 44     memset(belong,0,sizeof(belong)); 45     memset(g,0,sizeof(g)); 46 } 47 void addedge(int u,int v){ 48     edge[cnt].to=v; 49     edge[cnt].next=head[u]; 50     head[u]=cnt++; 51 } 52  53 void Tarjan(int u){ 54     dfn[u]=low[u]=++dep; 55     st[top++]=u; 56     vis[u]=1; 57     for(int i=head[u]; i!=-1; i=edge[i].next){ 58         int v=edge[i].to; 59         if(!dfn[v]){ 60             Tarjan(v); 61             low[u]=min(low[u],low[v]); 62         } 63         else if(vis[v]){ 64             low[u]=min(low[u],dfn[v]); 65         } 66     } 67     int j; 68     if(dfn[u]==low[u]){ 69         atype++; 70         do{ 71             j=st[--top]; 72             belong[j]=atype; 73             vis[j]=0; 74         } 75         while(u!=j); 76     } 77 } 78 int cas; 79 int main(){ 80    scanf("%d",&cas); 81    int tt=1; 82    while(cas--){ 83       scanf("%d%d",&n,&m); 84       init(); 85       for(int i=1;i<=n;i++){ 86           int temp; 87           scanf("%d",&temp); 88           for(int j=1;j<=temp;j++){ 89             scanf("%d",&u); 90             g[i][u]=1; 91           } 92       } 93         newn=n;newm=m; 94       int ans1=maxmatch(); 95        newn=n+m-ans1; 96        newm=n+m-ans1; 97       for(int i=n+1;i<=newn;i++){ 98           for(int j=1;j<=newm;j++) 99               g[i][j]=1;100       }101       for(int i=1;i<=newn;i++){102           for(int j=1+m;j<=newm;j++)103               g[i][j]=1;104       }105         maxmatch();106         memset(lx,-1,sizeof(lx));107       for(int i=1;i<=newm;i++){108           if(cy[i]!=-1)109             lx[cy[i]]=i;110       }111       for(int i=1;i<=newn;i++){112         for(int j=1;j<=newm;j++){113             if(g[i][j]&&j!=lx[i])114                 addedge(lx[i],j);115         }116       }117         for(int i=1;i<=newm;i++)118             if(!dfn[i])119               Tarjan(i);120         printf("Case #%d:\n",tt++);121         for(int i=1;i<=n;i++){122             ans.clear();123             for(int j = 1; j <= m;j++)124                 if(g[i][j] && belong[j] == belong[lx[i]])125                     ans.push_back(j);126             int sz = ans.size();127             printf("%d",sz);128             for(int i = 0;i < sz;i++)129                 printf(" %d",ans[i]);130             printf("\n");131         }132    }133 }
View Code

 


联系
我们