首页 > 代码库 > hdu 2768 Cat vs. Dog 最大独立集 巧妙的建图
hdu 2768 Cat vs. Dog 最大独立集 巧妙的建图
题目分析：
一个人要不是爱狗讨厌猫的人，要不就是爱猫讨厌狗的人。一个人喜欢的动物如果离开，那么他也将离开。问最多留下多少人。
思路：
爱猫和爱狗的人是两个独立的集合。若两个人喜欢和讨厌的动物是一样的，那么就建一条边。留下多少人，就是求最大独立集。
最大独立集= 顶点数 - 最大匹配数
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 const int N=505,INF=0x3f3f3f3f; 8 int bmap[N][N],cx[N],cy[N],dx[N],dy[N]; 9 bool bmask[N]; 10 int nx,ny,dis,ans; 11 bool searchpath() 12 { 13 queue<int> q; 14 dis=INF; 15 memset(dx,-1,sizeof(dx)); 16 memset(dy,-1,sizeof(dy)); 17 for(int i=1;i<=nx;i++) 18 { 19 if(cx[i]==-1){ q.push(i); dx[i]=0; } 20 while(!q.empty()) 21 { 22 int u=q.front(); q.pop(); 23 if(dx[u]>dis) break; 24 for(int v=1;v<=ny;v++) 25 { 26 if(bmap[u][v]&&dy[v]==-1) 27 { 28 dy[v]= dx[u] + 1; 29 if(cy[v]==-1) dis=dy[v]; 30 else 31 { 32 dx[cy[v]]= dy[v]+1; 33 q.push(cy[v]); 34 } 35 } 36 } 37 } 38 } 39 return dis!=INF; 40 } 41 int findpath(int u) 42 { 43 for(int v=1;v<=ny;v++) 44 { 45 if(!bmask[v]&&bmap[u][v]&&dy[v]==dx[u]+1) 46 { 47 bmask[v]=1; 48 if(cy[v]!=-1&&dy[v]==dis) continue; 49 if(cy[v]==-1||findpath(cy[v])) 50 { 51 cy[v]=u; cx[u]=v; 52 return 1; 53 } 54 } 55 } 56 return 0; 57 } 58 void maxmatch() 59 { 60 ans=0; 61 memset(cx,-1,sizeof(cx)); 62 memset(cy,-1,sizeof(cy)); 63 while(searchpath()) 64 { 65 memset(bmask,0,sizeof(bmask)); 66 for(int i=1;i<=nx;i++) 67 if(cx[i]==-1) ans+=findpath(i); 68 } 69 } 70 void init() 71 { 72 memset(bmap,0,sizeof(bmap)); 73 } 74 struct node 75 { 76 int x,y; 77 }c[N],d[N]; 78 int main() 79 { 80 //freopen("test.txt","r",stdin); 81 int cas,i,j,k,n,a,b; 82 char ch; 83 scanf("%d",&cas); 84 while(cas--) 85 { 86 scanf("%d%d%d",&a,&b,&n); 87 init(); 88 j=k=0; 89 for(i=1;i<=n;i++) 90 { 91 getchar(); 92 ch=getchar(); 93 if(ch==‘C‘) { 94 scanf("%d",&a); 95 c[j].x=a; 96 } 97 if(ch==‘D‘) { 98 scanf("%d",&a); 99 d[k].y=a;100 }101 scanf(" %c",&ch);102 if(ch==‘C‘) {103 scanf("%d",&a);104 d[k++].x=a;105 }106 if(ch==‘D‘) {107 scanf("%d",&a);108 c[j++].y=a;109 }110 }111 nx=j;ny=k;112 for(i=0;i<nx;i++){113 for(j=0;j<ny;j++){114 if(c[i].x==d[j].x||c[i].y==d[j].y)115 bmap[i+1][j+1]=1;116 }117 }118 maxmatch();119 printf("%d\n",n-ans);120 }121 return 0;122 }
hdu 2768 Cat vs. Dog 最大独立集 巧妙的建图
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。