[关闭]
@morehigh 2017-02-25T11:16:44.000000Z 字数 5089 阅读 1192

CQUPT 集训队专题训练（二分图）

二分图

最大匹配数：最大匹配的匹配边的数目

最小点覆盖数：选取最少的点，使任意一条边至少有一个端点被选择

最大独立数：选取最多的点，使任意所选两点均不相连

最小路径覆盖数：对于一个 DAG（有向无环图），选取最少条路径，使得每个顶点属于且仅属于一条路径。路径长可以为 0（即单个点）。

定理1：最大匹配数 = 最小点覆盖数（这是 Konig 定理）

定理2：最大独立集 = 顶点数 - 最大匹配数

定理3：最小路径覆盖数 = 顶点数 - 最大匹配数
A - COURSES
题意：

  1. 满足两个条件：
  2. 1.如果这个学生学习一门课程，可以作为这门课的代表
  3. 2.每门课程都有一个代表
  4. 输入t个案例，P (1 <= P <= 100)指有P门课程，N (1 <= N <= 300)指有N个学生，每门课程有若干个学生学习，若每门学生都有一个代表从输出“YES”，否则“NO”

解题思路：

  1. 让每门课与学习这门课的学生匹配，使每门课有各自不同的代表
  2. 匈牙利算法

代码：

  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <cmath>
  6. #include <queue>
  7. #include <vector>
  9. using namespace std;
  10. int map[105][305];
  11. int match[305];
  12. int use[305];
  13. int p,n;
  14. bool find(int x)
  15. {
  16.     for(int i=1;i<=n;i++)
  17.     {
  18.         if(!use[i]&&map[x][i])
  19.         {
  20.             use[i]=1;
  21.             if(match[i]==-1||find(match[i]))
  22.             {
  23.                 match[i]=x;
  24.                 return true;
  25.             }
  26.         }
  27.     }
  28.     return false;
  29. }
  30. int sol()
  31. {
  32.     int ans=0;
  33.     for(int i=1;i<=p;i++)
  34.     {
  35.         memset(use,0,sizeof(use));
  36.         if(find(i))
  37.         ans++;
  38.     }
  39.     return ans;
  40. }
  41. int main()
  42. {
  43.     int t,num,stu;
  44.     cin>>t;
  45.     while(t--)
  46.     {
  47.         memset(map,0,sizeof(map));
  48.         memset(match,-1,sizeof(match));
  49.         scanf("%d%d",&p,&n);
  50.         for(int i=1;i<=p;i++)
  51.         {
  52.             scanf("%d",&num);
  53.             for(int j=1;j<=num;j++)
  54.             {
  55.                 scanf("%d",&stu);
  56.                 map[i][stu]=1;
  57.             }
  58.         }
  59.         int ans=sol();
  60.         if(ans==p)
  61.         printf("YES\n");
  62.         else
  63.         printf("NO\n");
  64.     }
  65. }

B - The Accomodation of Students
题意：

  1. n(1<n<=200)个学生，m对学生相互认识，是这些同学分成两组，使组中同学相互不认识。，

解题思路：

  1. 先判断是否能将同学分成两组，是否为二分图，用染色法判断，将相互认识的同学连边，然后将连边的两个量标记为1，-1.若发现相邻一样，则表明出现环，则不是二分图。若是二分图，则匈牙利算法求最大匹配

代码：

  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <cmath>
  6. #include <vector>
  8. using namespace std;
  9. int n,m;
  10. int use[500],match[500];
  11. int d[500];
  12. vector<int> mp[500];
  13. int dfs(int x,int f)
  14. {
  15.     d[x]=f;
  16.     for(int i=0;i<mp[x].size();i++)
  17.     {
  18.         if(d[x]==d[mp[x][i]])
  19.         return 0;
  20.         if(d[mp[x][i]]==0)
  21.         {
  22.         //  d[mp[x][i]]=-f;
  23.             if(!dfs(mp[x][i],-f))
  24.             return 0;
  25.         }
  26.     }
  27.     return 1;
  28. }
  29. int find(int x)
  30. {
  31.     for(int i=0;i<mp[x].size();i++)
  32.     {
  33.         int y=mp[x][i];
  34.         if(!use[y])
  35.         {
  36.             use[y]=1;
  37.             if(match[y]==-1||find(match[y]))
  38.             {
  39.                 match[y]=x;
  40.                 return 1;
  41.             }
  42.         }
  43.     }
  44.     return 0;
  45. }
  46. int solve()
  47. {
  48.     int ans=0;
  49.     for(int i=1;i<=n;i++)
  50.     {
  51.         memset(use,0,sizeof(use));
  52.         if(find(i))
  53.         ans++;
  54.     }
  55.     return ans;
  56. }
  57. int main()
  58. {
  59.     int a,b;
  60.     while(scanf("%d%d",&n,&m)!=EOF)
  61.     {
  62.         memset(match,-1,sizeof(match));
  63.         for(int i=1;i<=n;i++)
  64.         if(mp[i].size())
  65.         mp[i].clear();
  66.         for(int i=0;i<m;i++)
  67.         {
  68.             scanf("%d%d",&a,&b);
  69.             mp[a].push_back(b); 
  70.             mp[b].push_back(a); 
  71.         }
  72.         int flag=1;
  73.         memset(d,0,sizeof(d));
  74.         for(int i=1;i<=n;i++)
  75.         {
  76.             if(mp[i].size())
  77.              if(!d[i])
  78.                if(!dfs(i,1))
  79.                {
  80.                 flag=0;
  81.                 break;
  82.                }
  83.         }
  84.         if(!flag)
  85.         cout<<"No"<<endl;
  86.         else
  87.         {
  88.             cout<<solve()/2<<endl;
  89.         }
  90.     }
  91.     return 0;
  92. }

C - Guardian of Decency
题意：

  1. 老师要带一些同学去春游，为了防止同学之间早恋，若满足4个条件之一，则2个同学将发生早恋。T ≤ 100组样例，N ≤ 500名学生，然后每个同学4个属性。

解题思路：

  1. 二分图的最小独立集=点集-最大匹配，将满足4个条件能成为恋人的两人连线，得到最大匹配。

代码：

  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <cmath>
  7. using namespace std;
  8. int n;
  9. int ff,mm;
  10. int map[510][510],match[510],use[510];
  11. struct Node
  12. {
  13.     int h;
  14.     char sex[2];
  15.     char mus[105],sp[105];
  16. }pup[510];
  17. int find(int x)
  18. {
  19.     for(int i=0;i<n;i++)
  20.     {
  21.         if(!use[i]&&map[x][i])
  22.         {
  23.             use[i]=1;
  24.             if(match[i]==-1||find(match[i]))
  25.             {
  26.                 match[i]=x;
  27.                 return 1;
  28.             }
  29.         }
  30.     }
  31.     return 0;
  32. }
  33. int solve()
  34. {
  35.     int ans=0;
  36.     for(int i=0;i<n;i++)
  37.     {
  38.         memset(use,0,sizeof(use));
  39.         if(find(i))
  40.         ans++;
  41.     }
  42.     return ans;
  43. }
  44. int main()
  45. {
  46.     int t;
  47.     cin>>t;
  48.     while(t--)
  49.     {
  50.         scanf("%d",&n);
  51.         int h;
  52.     //  ff=0,mm=0;
  53.     //  char sex[2];
  54.     //  char mus[105],sp[105];
  55.         for(int i=0;i<n;i++)
  56.         {
  57.             scanf("%d%s%s%s",&pup[i].h,pup[i].sex,pup[i].mus,pup[i].sp);
  58.         //  printf("%d%s%s%s",h,sex,mus,sp);
  59.         }
  60.         memset(match,-1,sizeof(match));
  61.         memset(map,0,sizeof(map));
  62.         for(int i=0;i<n;i++)
  63.         {
  64.             for(int j=0;j<n;j++)
  65.             {
  66.                 if(abs(pup[i].h-pup[j].h)<=40&&strcmp(pup[i].mus,pup[j].mus)==0&&strcmp(pup[i].sp,pup[j].sp)!=0&&strcmp(pup[i].sex,pup[j].sex)!=0)
  67.                 map[i][j]=map[j][i]=1;
  68.             }
  69.         }
  70.         int ans=solve()/2;
  71.         printf("%d\n",n-ans);
  72.     }
  73.     return 0;
  74. }

D - Machine Schedule
题意：

  1. n, m (n, m < 100)，2台机器，第一台有n中模式，第二台有m种模式，有k个任务每个任务只能限定每一台机器只有一种模式能够工作，若要重启一次需要花费1的时间。求最少重启几次。

解题思路：

  1. 二分图的最小点覆盖=最大匹配。
  2. 二分匹配时，一边是第一台机器n种模式，另一边是第二台机器的m种模式，转换一种模式时就要重启一次因此遍历第一台的每个模式求出最大匹配就是重启多少次

代码：

  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <cmath>
  7. using namespace std;
  8. int n,m,k;
  9. int map[110][110],match[110],use[110];
  10. int find(int x)
  11. {
  12.     for(int i=0;i<m;i++)
  13.     {
  14.         if(!use[i]&&map[x][i])
  15.         {
  16.             use[i]=1;
  17.             if(match[i]==-1||find(match[i]))
  18.             {
  19.                 match[i]=x;
  20.                 return 1;
  21.             }
  22.         }
  23.     }
  24.     return 0;
  25. }
  26. int solve()
  27. {
  28.     int ans=0;
  29.     for(int i=0;i<n;i++)
  30.     {
  31.         memset(use,0,sizeof(use));
  32.         if(find(i))
  33.         ans++;
  34.     }
  35.     return ans;
  36. }
  37. int main()
  38. {
  39.     int j,x,y;
  40.     while(scanf("%d",&n)!=EOF&&n)
  41.     {
  42.         scanf("%d%d",&m,&k);
  43.         memset(map,0,sizeof(map));
  44.         memset(match,-1,sizeof(match));
  45.         for(int i=0;i<k;i++)
  46.         {
  47.             scanf("%d%d%d",&j,&x,&y);
  48.             if(x>0&&y>0)
  49.             map[x][y]=1;
  50.         }
  51.         cout<<solve()<<endl;
  52.     }
  53.     return 0;
  54. }

E - Cat VS Dog
题意：

  1. P个小朋友去参观动物园，动物园中有N只猫和M只狗，每个小朋友都会有喜欢一只狗（或猫），讨厌一只猫（或狗），饲养员要带走一些猫或者狗，然而带走一个小朋友喜欢的动物，小朋友会不开心，为了使更多小朋友开心，问最多使多少小朋友开心

解题思路：

  1. 二分图最大点独立集 = 顶点数 - 最大匹配数，对同一只动物喜欢和不喜欢的小朋友进行匹配，说明这两个小朋友具有排斥关系，由于我们是将每个小朋友都匹配一次，所以应该小朋友数-匹配数/2.

代码：

  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <cmath>
  7. using namespace std;
  8. int n,m,k;
  9. int map[510][510],match[510],use[510];
  10. char lk[510][10],dislk[510][10];
  11. int find(int x)
  12. {
  13.     for(int i=0;i<k;i++)
  14.     {
  15.         if(!use[i]&&map[x][i])
  16.         {
  17.             use[i]=1;
  18.             if(match[i]==-1||find(match[i]))
  19.             {
  20.                 match[i]=x;
  21.                 return 1;
  22.             }
  23.         }
  24.     }
  25.     return 0;
  26. }
  27. int solve()
  28. {
  29.     int ans=0;
  30.     for(int i=0;i<k;i++)
  31.     {
  32.         memset(use,0,sizeof(use));
  33.         if(find(i))
  34.         ans++;
  35.     }
  36. //  cout<<ans<<endl;
  37.     return ans;
  38. }
  39. int main()
  40. {
  41.     int j,x,y;
  42.     while(scanf("%d%d%d",&n,&m,&k)!=EOF)
  43.     {
  44.         memset(map,0,sizeof(map));
  45.         memset(match,-1,sizeof(match));
  46.         for(int i=0;i<k;i++)
  47.         {
  48.             scanf("%s%s",lk[i],dislk[i]);
  49.         }
  50.         for(int i=0;i<k;i++)
  51.         {
  52.             for(int j=0;j<k;j++)
  53.             {
  54.                 if(strcmp(lk[i],dislk[j])==0||strcmp(lk[j],dislk[i])==0)
  55.                 map[i][j]=map[j][i]=1;
  56.             }
  57.         }
  58.         cout<<k-solve()/2<<endl;
  59.     }
  60.     return 0;
  61. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注