Prince and Princess
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 优质内容筛选与推荐>>
1、DIV垂直居中
2、[Java学习] Java异常处理基础
3、第三次作业——结对编程
4、解决samba和SELINUX 冲突
5、HAService 刨坑