[关闭]
@TryMyEdge 2017-02-11T16:26:26.000000Z 字数 8150 阅读 976

专题六(二分图)

题解

题目

A COURSES

题目大意：

    有P(1<=P<=100)门课程，N(1<=N<=300)名学生，第i门课程有Ci(0<=Ci<=N)名学生有当课代表的资格，其中第j名学生的编号为Sij。问是否能在每名学生最多当一门课的课代表的情况下为每一门课都安排一个课代表。
    T组数据。

解题思路：

    二分图匹配裸题。
    每门课程和课代表候选人连边，跑最大匹配。我用的是匈牙利算法。
    时间复杂度o(T*P*sum(C))，空间复杂度o(P*N)。

AC代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #define pq priority_queue
  5. #define Pi acos(-1.0)
  6. using namespace std;
  7. #define MOD 1000000007
  8. int maps[105][305],nums[105];
  9. int life[305];
  10. bool used[305];
  11. int p,n;
  12. bool ok(int x)
  13. {
  14.     for(int i=0;i<nums[x];i++)
  15.     {
  16.         if(!used[maps[x][i]])
  17.         {
  18.             used[maps[x][i]]=1;
  19.             if(!life[maps[x][i]] || ok(life[maps[x][i]]))
  20.             {
  21.                 life[maps[x][i]]=x;
  22.                 return 1;
  23.             }
  24.         }
  25.     }
  26.     return 0;
  27. }
  28. int main()
  29. {
  30.     int T,ans;
  31.     cin>>T;
  32.     for(int t=1;t<=T;t++)
  33.     {
  34.         memset(nums,0,sizeof(nums));
  35.         memset(life,0,sizeof(life));
  36.         ans=0;
  37.         scanf("%d%d",&p,&n);
  38.         for(int i=1;i<=p;i++)
  39.         {
  40.             scanf("%d",nums+i);
  41.             for(int j=0;j<nums[i];j++)
  42.                 scanf("%d",&maps[i][j]);
  43.         }
  44.         for(int i=1;i<=p;i++)
  45.         {
  46.             memset(used,0,sizeof(used));
  47.             if(ok(i))
  48.                 ans++;
  49.         }
  50.         if(ans==p)
  51.             printf("YES\n");
  52.         else
  53.             printf("NO\n");
  54.     }
  55.     return 0;
  56. }

B The Accomodation of Students

题目大意：

    有n(1<n<=200)名学生，其中m对学生互相认识。求能不能将学生分为两个组，使得组内的学生互相之前都不直接认识。如果能，将两名互相认识的学生安排到一个双人间，求最多能安排多少间双人间。
    多组数据。

解题思路：

    首先将互相认识的学生连边，然后判断是不是二分图。我用的方法是bfs染色，如果一个点未染色，将它染成颜色1，并且将它所有未染色的邻接点染为颜色2，然后把这些邻接点加入队列。每次从队头取出一个点，把他的所有未染色的邻接点染为另一个颜色再加入队列，重复这个操作直到所有点都被染色。如果某个邻接点已染色而且跟当前点颜色一样，说明出现了奇环，就可以判断不是二分图。
    如果是二分图，那么两种颜色的点就是二分图的两个点集，跑一次最大匹配即可。
    时间复杂度o(n*m)，空间复杂度o(n^2)。

AC代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<queue>
  5. #define pq priority_queue
  6. #define Pi acos(-1.0)
  7. using namespace std;
  8. #define MOD 1000000007
  9. int maps[205][205],nums[205];
  10. int life[205];
  11. bool used[205];
  12. int color[205];
  13. queue <int> q;
  14. int m,n;
  15. bool ok(int x)
  16. {
  17.     for(int i=0;i<nums[x];i++)
  18.     {
  19.         if(!used[maps[x][i]])
  20.         {
  21.             used[maps[x][i]]=1;
  22.             if(!life[maps[x][i]] || ok(life[maps[x][i]]))
  23.             {
  24.                 life[maps[x][i]]=x;
  25.                 return 1;
  26.             }
  27.         }
  28.     }
  29.     return 0;
  30. }
  31. int main()
  32. {
  33.     int ans,a,b,gg;
  34.     bool flag;
  35.     while(~scanf("%d%d",&n,&m))
  36.     {
  37.         memset(nums,0,sizeof(nums));
  38.         memset(life,0,sizeof(life));
  39.         memset(color,0,sizeof(color));
  40.         ans=0;
  41.         flag=0;
  42.         for(int i=1;i<=m;i++)
  43.         {
  44.             scanf("%d%d",&a,&b);
  45.             maps[a][nums[a]++]=b;
  46.             maps[b][nums[b]++]=a;
  47.         }
  48.         for(int i=1;i<=n;i++)
  49.         {
  50.             if(!color[i])
  51.             {
  52.                 color[i]=1;
  53.                 q.push(i);
  54.                 while(!q.empty())
  55.                 {
  56.                     gg=q.front();
  57.                     q.pop();
  58.                     for(int j=0;j<nums[gg];j++)
  59.                     {
  60.                         if(!color[maps[gg][j]])
  61.                         {
  62.                             color[maps[gg][j]]=-color[gg];
  63.                             q.push(maps[gg][j]);
  64.                         }
  65.                         else
  66.                             flag|=color[maps[gg][j]]==color[gg];
  67.                     }
  68.                 }
  69.             }
  70.         }
  71.         if(flag)
  72.             printf("No\n");
  73.         else
  74.         {
  75.             for(int i=1;i<=n;i++)
  76.             {
  77.                 if(color[i]==1)
  78.                 {
  79.                     memset(used,0,sizeof(used));
  80.                     if(ok(i))
  81.                         ans++;
  82.                 }
  83.             }
  84.             printf("%d\n",ans);
  85.         }
  86.     }
  87.     return 0;
  88. }

C Guardian of Decency

题目大意：

    有N(N<=500)名学生，老师要带他们出去玩，但是要防止他们早恋。
    两名学生如果符合以下四个条件中的任意一条，就认为他们谈恋爱的可能性很低：
    (1)身高差超过40cm(这么高的身高怕是只有冯杰聚聚能达到。。。
    (2)性别相同(滑稽
    (3)喜欢的音乐风格不同
    (4)喜欢的运动相同
    现在给出每名学生的身高、性别、喜欢的音乐风格、喜欢的运动，问在保证没有任何一对学生有谈恋爱的可能性的情况下，老师最多能带多少名学生出去玩。
    T(T<=100)组数据。

解题思路：

    先讲一个定义：最大独立集。从一张二分图中选择一些点，满足被选中的任意两个点之间都没有边，所选择的最多的点数称为二分图的最大独立集。
    再讲一个定理：二分图的最小独立集=点集-最大匹配。具体证明网上有大家有兴趣可以去看一看。
    回到这道题，我们如果我们在所有有可能谈恋爱的学生之间连边，因为同性别不可能连边，所以我们可以按性别将学生们分成两个集合，这样原图就是一张二分图，我们要做的就是求他的最大独立集。
    连边建图，按性别分好点集，跑出最大匹配之后用定理求出答案。
    小细节：使用邻接表来进行图的储存在时间性能上相比邻接矩阵有很大优势。
    时间复杂度o(T*N^3)，空间复杂度o(N^2)。

AC代码：

  1. #include<iostream>
  2. #include<cmath>
  3. #include<string>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<queue>
  7. #define pq priority_queue
  8. #define Pi acos(-1.0)
  9. using namespace std;
  10. #define MOD 1000000007
  11. struct Pupils
  12. {
  13.     int h;
  14.     char a[105],b[105];
  15. }p[505];
  16. int maps[505][505],nums[505];
  17. int life[505];
  18. bool used[505];
  19. int n;
  20. int num1,num2,p1[505],p2[505];
  21. bool ok(int x)
  22. {
  23.     for(int i=0;i<nums[x];i++)
  24.     {
  25.         if(!used[maps[x][i]])
  26.         {
  27.             used[maps[x][i]]=1;
  28.             if(!life[maps[x][i]] || ok(life[maps[x][i]]))
  29.             {
  30.                 life[maps[x][i]]=x;
  31.                 return 1;
  32.             }
  33.         }
  34.     }
  35.     return 0;
  36. }
  37. int main()
  38. {
  39.     int ans,T;
  40.     char sex[6];
  41.     bool flag;
  42.     cin>>T;
  43.     while(T--)
  44.     {
  45.         memset(nums,0,sizeof(nums));
  46.         memset(life,0,sizeof(life));
  47.         ans=0;
  48.         num1=0;
  49.         num2=0;
  50.         scanf("%d",&n);
  51.         for(int i=1;i<=n;i++)
  52.         {
  53.             scanf("%d%s%s%s",&p[i].h,&sex,p[i].a,p[i].b);
  54.             if(sex[0]=='M')
  55.                 p1[num1++]=i;
  56.             else
  57.                 p2[num2++]=i;
  58.         }
  59.         for(int i=0;i<num1;i++)
  60.         {
  61.             for(int j=0;j<num2;j++)
  62.             {
  63.                 if(abs(p[p1[i]].h-p[p2[j]].h)<=40  && !strcmp(p[p1[i]].a,p[p2[j]].a) && strcmp(p[p1[i]].b,p[p2[j]].b))
  64.                     maps[p1[i]][nums[p1[i]]++]=p2[j];
  65.             }
  66.         }
  67.         for(int i=0;i<num1;i++)
  68.         {
  69.             memset(used,0,sizeof(used));
  70.             if(ok(p1[i]))
  71.                 ans++;
  72.         }
  73.         printf("%d\n",n-ans);
  74.     }
  75.     return 0;
  76. }

D Machine Schedule

题目大意：

    有两台机器，第一台有n(n<100)种工作模式，分别是0到n-1，第二台有m(m<100)种工作模式，分别是0到m-1。现在有k(k<1000)个任务，第i个任务可以用第一台机器的Ai(0<=ai<=n-1)模式解决或者用第二台机器的Bi(0<=bi<=m-1)模式解决。一开始两台机器都在0模式，问以任意顺序解决这k个任务两台机器一共需要改变模式最少多少次。
    多组数据，n=0表示结束。

解题思路：

    因为顺序可以随便决定，那么我们肯定是把相同模式能解决的问题一起搞定了，所以问题实际上是每个任务选择在哪一台机器上解决，可以让除了0之外需要的模式总数最少。枚举每个任务的选择肯定是不可能枚举的，这辈子都跑不出来。。。
    (又)先讲一个定义：最小点覆盖。在二分图中选择一些点，满足每条边的两个端点中至少有一个点被选中，选择的最少点数成为最小点覆盖。
    再讲一个定理：二分图的最小点覆盖=最大匹配。对证明有兴趣的同样去网上找。。。
    把两台机器的模式作为两个点集，对于每个任务的两个端点连边，跑最大匹配。
    小细节：因为初始模式为0，所以所有可以在某台机器的0模式下解决的任务都直接用0模式解决，所以这些边就可以不连。可能会出现多个任务所连的两个点是相同的，所以如果直接用二维数组表示的邻接表存图，应该开n*k而不是n*m。这里我是用一个二维bool数组来记录点之间的邻接情况来避免重复连边的(实际上就是邻接矩阵)。
    时间复杂度o(n*k)，空间复杂度o(n*m)。

AC代码：

  1. #include<iostream>
  2. #include<cmath>
  3. #include<string>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<queue>
  7. #define pq priority_queue
  8. #define Pi acos(-1.0)
  9. using namespace std;
  10. #define MOD 1000000007
  11. struct Pupils
  12. {
  13.     int h;
  14.     char a[105],b[105];
  15. }p[505];
  16. int maps[105][105],nums[105];
  17. bool gg[105][105];
  18. int life[105];
  19. bool used[105];
  20. bool ok(int x)
  21. {
  22.     for(int i=0;i<nums[x];i++)
  23.     {
  24.         if(!used[maps[x][i]])
  25.         {
  26.             used[maps[x][i]]=1;
  27.             if(!life[maps[x][i]] || ok(life[maps[x][i]]))
  28.             {
  29.                 life[maps[x][i]]=x;
  30.                 return 1;
  31.             }
  32.         }
  33.     }
  34.     return 0;
  35. }
  36. int main()
  37. {
  38.     int ans,n,m,k,a,b;
  39.     while(scanf("%d",&n),n)
  40.     {
  41.         scanf("%d%d",&m,&k);
  42.         memset(nums,0,sizeof(nums));
  43.         memset(life,0,sizeof(life));
  44.         memset(gg,0,sizeof(gg));
  45.         for(int i=0;i<k;i++)
  46.         {
  47.             scanf("%d%d%d",&ans,&a,&b);
  48.             if(a && b)
  49.             {
  50.                 if(!gg[a][b])
  51.                 {
  52.                     gg[a][b]=1;
  53.                     maps[a][nums[a]++]=b;
  54.                 }
  55.             }
  56.         }
  57.         ans=0;
  58.         for(int i=1;i<n;i++)
  59.         {
  60.             memset(used,0,sizeof(used));
  61.             if(ok(i))
  62.                 ans++;
  63.         }
  64.         printf("%d\n",ans);
  65.     }
  66.     return 0;
  67. }

E Cat VS Dog

题目大意：

    动物园有N(N<=100)只猫，M(M<=100)只狗。有P(P<=500)个小朋友来动物园玩，每个小朋友有自己最喜欢的小动物和自己最讨厌的小动物，这两者一定一猫一狗。如果他最喜欢的小动物不在动物园或者他最讨厌的小动物在动物园，那么他就会不高兴。你现在可以选择留下某些小动物在动物园中，问最多能让多少小朋友高兴。

解题思路：

    很有迷惑性的一道题。如果去考虑在猫和狗之间连边，那么我们会发现，一只猫和一只狗共存是否矛盾，是受要让具体哪些小朋友高兴影响的，而不是固定的。但是反过来想，两名小朋友同时高兴是否矛盾则是固定的。因此我们采用以小朋友为点集，对冲突的小朋友连边的方式来建图。
    建出来的图一定是二分图。为什么？因为如果A和B两个小朋友冲突，那么至少满足以下两种可能性中的一种：(1)A最喜欢是B最讨厌的，(2)A最讨厌的是B最喜欢的。我们不难看出，如果两个小朋友冲突，那么他们喜欢和讨厌的动物种类肯定是相反的，于是我们把小朋友按照喜欢的动物的种类划分为两个点集，同个点集内肯定不会出现边，所以就满足了二分图的要求。
    显而易见我们要求的是二分图的最大独立集，建图之后跑最大匹配即可。
    时间复杂度o(P^3)，空间复杂度o(P^2)。

AC代码：

  1. #include<iostream>
  2. #include<cmath>
  3. #include<string>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<queue>
  7. #define pq priority_queue
  8. #define Pi acos(-1.0)
  9. using namespace std;
  10. #define MOD 1000000007
  11. struct Pupils
  12. {
  13.     char a[6],b[6];
  14. }p[505];
  15. int maps[505][505],nums[505];
  16. int life[505];
  17. bool used[505];
  18. bool ok(int x)
  19. {
  20.     for(int i=0;i<nums[x];i++)
  21.     {
  22.         if(!used[maps[x][i]])
  23.         {
  24.             used[maps[x][i]]=1;
  25.             if(!life[maps[x][i]] || ok(life[maps[x][i]]))
  26.             {
  27.                 life[maps[x][i]]=x;
  28.                 return 1;
  29.             }
  30.         }
  31.     }
  32.     return 0;
  33. }
  34. int main()
  35. {
  36.     int ans,n,m,k,a,b;
  37.     while(~scanf("%d%d%d",&n,&m,&k))
  38.     {
  39.         memset(nums,0,sizeof(nums));
  40.         memset(life,0,sizeof(life));
  41.         for(int i=1;i<=k;i++)
  42.             scanf("%s%s",p[i].a,p[i].b);
  43.         for(int i=1;i<=k;i++)
  44.         if(p[i].a[0]=='C')
  45.         {
  46.             for(int j=1;j<=k;j++)
  47.             {
  48.                 if(!strcmp(p[i].a,p[j].b) || !strcmp(p[i].b,p[j].a))
  49.                     maps[i][nums[i]++]=j;
  50.             }
  51.         }
  52.         ans=0;
  53.         for(int i=1;i<=k;i++)
  54.         if(p[i].a[0]=='C')
  55.         {
  56.             memset(used,0,sizeof(used));
  57.             if(ok(i))
  58.                 ans++;
  59.         }
  60.         printf("%d\n",k-ans);
  61.     }
  62.     return 0;
  63. }

F Antenna Placement

题目大意：

    在一张高为h(1<=h<=40)，宽为w（0<w<=10）的地图上，有一些目标点(正在占领目标点.jpg)，一个天线可以横着或者竖着覆盖两个相邻的目标点，但不能斜着。问最少需要多少个个天线才能覆盖所有目标点。
    T组数据。

解题思路：
我是图

    我们把地图按斜着切成一条一条的(见上图)，我们会发现红色那条里面的目标点只有可能和蓝色里面的被同一个天线覆盖(自古红蓝出cp)。
    于是把点按图上的红蓝划分成两个点集，然后把横着或者竖着相邻的两个目标点连边。显然我们求的是最小点覆盖，跑个最大匹配就可以了。
    小细节：注意必须是两个点都是目标点的情况才能连边，跑最大匹配的时候只在当前点是目标点的情况下才去进行增广。建图的时候我把每个点按坐标算了一个编号，挺好用的处理方法大家可以参考一下。
    时间复杂度o(T*(h*w)^2)，空间复杂度o((h*w)^2)。

AC代码：

  1. #include<iostream>
  2. #include<cmath>
  3. #include<string>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<queue>
  7. #define pq priority_queue
  8. #define Pi acos(-1.0)
  9. using namespace std;
  10. #define MOD 1000000007
  11. int maps[405][405],nums[405];
  12. char ditu[45][15];
  13. int life[405];
  14. bool used[405];
  15. bool ok(int x)
  16. {
  17.     for(int i=0;i<nums[x];i++)
  18.     {
  19.         if(!used[maps[x][i]])
  20.         {
  21.             used[maps[x][i]]=1;
  22.             if(!life[maps[x][i]] || ok(life[maps[x][i]]))
  23.             {
  24.                 life[maps[x][i]]=x;
  25.                 return 1;
  26.             }
  27.         }
  28.     }
  29.     return 0;
  30. }
  31. int main()
  32. {
  33.     int T,ans,h,w;
  34.     cin>>T;
  35.     while(T--)
  36.     {
  37.         memset(nums,0,sizeof(nums));
  38.         memset(life,0,sizeof(life));
  39.         scanf("%d%d",&h,&w);
  40.         for(int i=0;i<h;i++)
  41.             scanf("%s",ditu[i]+1);
  42.         ans=0;
  43.         for(int i=0;i<h;i++)
  44.             for(int j=1;j<=w;j++)
  45.             {
  46.                 if(ditu[i][j]!='*')
  47.                     continue;
  48.                 ans++;
  49.                 if((i+j)%2)
  50.                 {
  51.                     if(i>0 && ditu[i-1][j]=='*')
  52.                         maps[i*w+j][nums[i*w+j]++]=(i-1)*w+j;
  53.                     if(i+1<h && ditu[i+1][j]=='*')
  54.                         maps[i*w+j][nums[i*w+j]++]=(i+1)*w+j;
  55.                     if(j>1 && ditu[i][j-1]=='*')
  56.                         maps[i*w+j][nums[i*w+j]++]=i*w+j-1;
  57.                     if(j<w && ditu[i][j+1]=='*')
  58.                         maps[i*w+j][nums[i*w+j]++]=i*w+j+1;
  59.                 }
  60.             }
  61.         for(int i=0;i<h;i++)
  62.             for(int j=1;j<=w;j++)
  63.             if(ditu[i][j]=='*' && (i+j)%2)
  64.             {
  65.                 memset(used,0,sizeof(used));
  66.                 if(ok(i*w+j))
  67.                     ans--;
  68.             }
  69.         printf("%d\n",ans);
  70.     }
  71.     return 0;
  72. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注