Hdu 5285 wyh2000 and pupil (bfs染色判断奇环) (二分图匹配)

题目链接：

题目描述：

　　n个小朋友要被分成两班，但是有些小朋友之间是不认得的，所以规定不能把不认识的小朋友分在一个班级里面，并且一班的人数要比二班的人数多，每个班的人数都大于零。

解题思路：

　　hdu给出的题解是二分图匹配加上贪心，就不多说了。

　　还可以用bfs对节点染色，建好图后，对节点进行bfs分成，偶数成与奇数成染成不同的颜色，颜色相同的节点都可以分到同一个集合里面，但是要判断一下奇环，如果出现奇环的话，是无法进行分组的。在每次bfs的时候再加上贪心累计求和。

 #include <queue>

 #include <vector>

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 vector < int > G[maxn];

 int x, y, n, m, vis[maxn], flag;

 void bfs (int s)

 {

     int p, q, zreo, one, num;

     queue <int> Q;

     zreo = ;

     one = vis[s] = ;

     Q.push(s);

     while (!Q.empty())

     {

         p = Q.front();

         Q.pop();

         num = (vis[p] + ) % ;

         for (int i=; i<G[p].size(); i++)

         {

             q = G[p][i];

             if (vis[q]!=- && num != vis[q])

                 flag = ;

             if (vis[q]==-)

             {

                 Q.push(q);

                 vis[q] = num;

                 if (num == )

                     zreo ++;

                 else

                     one ++;

             }

         }

     }

     x += max (zreo, one);

     y += min (one, zreo);

 }

 int main ()

 {

     int t;

     scanf ("%d", &t);

     while (t --)

     {

         scanf ("%d %d", &n, &m);

         memset (vis, -, sizeof(vis));

         for (int i=; i<=n; i++)

             G[i].clear();

         x = y = flag = ;

         while (m --)

         {

             int a, b;

             scanf ("%d %d", &a, &b);

             G[a].push_back (b);

             G[b].push_back (a);

         }

         for (int i=; i<=n; i++)

         {

             if (vis[i] == -)

                 bfs (i);

             if (flag)

                 break;

         }

         if (x == n)

         {

             x --;

             y ++;

         }

         if (flag || x <  || y < )

             printf ("Poor wyh\n");

         else

             printf ("%d %d\n", x, y);

     }

     return ;

 }

用二分图匹配要比bfs快一半，内存也要少好多，所以再贴一个二分图匹配的代码：

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <iostream>

 using namespace std;

 const int maxn = ;

 struct Edge

 {

     int to, next;

 }edge[*maxn];

 int tot, head[maxn], vis[maxn];

 void init ()

 {

     tot = ;

     memset (head, -, sizeof(head));

 }

 void Add (int from, int to)

 {

     edge[tot].to = to;

     edge[tot].next = head[from];

     head[from] = tot ++;

 }

 bool dfs (int x, int c, int &a, int &b)

 {

     b ++;

     if (c)

         a ++;

     vis[x] = c;

     for (int i=head[x]; i!=-; i=edge[i].next)

     {

         int num = edge[i].to;

         if (vis[num] == c)

             return false;

         if (vis[num] == - && !dfs(num, c^, a, b))

             return false;

     }

     return true;

 }

 int main ()

 {

     int t, n, m;

     scanf ("%d", &t);

     while (t --)

     {

         scanf ("%d %d", &n, &m);

         init ();

         while (m --)

         {

             int a, b;

             scanf ("%d %d", &a, &b);

             Add (a, b);

             Add (b, a);

         }

         int x, y;

         bool flag = true;

         memset (vis, -, sizeof(vis));

         x = y = ;

         for (int i=; i<=n; i++)

         {

             int a, b;

             a = b = ;

             if (vis[i] == -)

             {

                 if (!dfs (i, , a, b))

                 {

                     flag = false;

                     break;

                 }

             }

             x += max (a, b - a);

             y += min (a, b - a);

         }

         if (x == n)

         {

             x --;

             y ++;

         }

         if (!flag || x< || y<)

             printf ("Poor wyh\n");

         else

             printf ("%d %d\n", x, y);

     }

     return ;

 }

巴特西

Hdu 5285 wyh2000 and pupil (bfs染色判断奇环) (二分图匹配)

最新文章

热门文章