50 years, 50 colors(HDOJ 1498)

Problem Description

On Octorber 21st, HDU 50-year-celebration, 50-color balloons floating around the campus, it's so nice, isn't it? To celebrate this meaningful day, the ACM team of HDU hold some fuuny games. Especially, there will be a game named "crashing color balloons".

There will be a n*n matrix board on the ground, and each grid will have a color balloon in it.And the color of the ballon will be in the range of [1, 50].After the referee shouts "go!",you can begin to crash the balloons.Every time you can only choose one kind of balloon to crash, we define that the two balloons with the same color belong to the same kind.What's more, each time you can only choose a single row or column of balloon, and crash the balloons that with the color you had chosen. Of course, a lot of students are waiting to play this game, so we just give every student k times to crash the balloons.

Here comes the problem: which kind of balloon is impossible to be all crashed by a student in k times.

Input

There will be multiple input cases.Each test case begins with two integers n, k. n is the number of rows and columns of the balloons (1 <= n <= 100), and k is the times that ginving to each student(0 < k <= n).Follow a matrix A of n*n, where Aij denote the color of the ballon in the i row, j column.Input ends with n = k = 0.

Output

 For each test case, print in ascending order all the colors of which are impossible to be crashed by a student in k times. If there is no choice, print "-1".

Sample Input

1 1
1
2 1
1 1
1 2
2 1
1 2
2 2
5 4
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4
3 3
50 50 50
50 50 50
50 50 50
0 0

Sample Output

-1
1
2
1 2 3 4 5
-1

My Code

这题题意不大好理解，大概意思就是你每次可以选择将一行或者一列的同种颜色的气球踩爆，问你能否在K次内把某颜色的气球全部踩爆。再加上上一题，我们可以发现，对于一次处理一行或一列的题目，可以尝试一下二分图的方法。这题其实就是将每种颜色建一张二分图，而二分图的最大匹配数，就是踩爆该颜色所有气球所需的次数，然后和k比较一下就行了。

#include 
#include 

using namespace std;
int n, m, k;
int linker[150];
int map[150][150];
bool vis[150];
int cnt;
bool v[150];
bool dfs(int u, int color)
{
    for (int i = 0; i < n; i++)
        if (map[u][i] == color && !vis[i])
        {
            vis[i] = 1;
            if (linker[i] == -1 || dfs(linker[i], color)) //如果i没有对象或者i的对象还能找到其他对象
            {                                             //那么u和i就匹配
                linker[i] = u;
                return true;
            }
        }
    return false;
}
void hungary(int color)
{
    cnt = 0;
    memset(linker, -1, sizeof(linker));
    for (int i = 0; i < n; i++)
    {
        memset(vis, false, sizeof(vis)); //因为别人找过的对象你也还可以去试试，所以每次都要清空
        if (dfs(i, color))               //如果i能找到对象，匹配数++
            cnt++;
    }
}
int main()
{
    while (cin >> n >> k && n && k)
    {
        memset(map, 0, sizeof(map));
        memset(v, false, sizeof(v));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                cin >> map[i][j];
                v[map[i][j]] = 1;       //标记一下有哪些颜色
            }
        bool flag = 0;
        for (int i = 1; i <= 50; i++)
            if (v[i])
            {
                hungary(i);
                if (cnt > k)           //最大匹配数cnt就是把气球弄爆所需的最少次数
                {
                    if (flag)
                        cout << ' ' << i;
                    else
                    {
                        flag = 1;
                        cout << i;
                    }
                }
            }
        if (!flag)
            cout << -1;
        cout << endl;
    }
}