題敘

平面的網格裡上有一些點，每次可以把一直排或橫排消掉，
問最少要幾次。

想法

發現對於所有點對$(u, v)$，至少要滿足$x_u + y_v \geq 1$， 也就是說把$x$畫一邊，$y$畫一邊，中間的所有邊都至少要一個點有被選到，
原題就是二分圖最小點覆蓋，也就是二分圖最大匹配

所以Code就是最大匹配的過程，每次看有沒有辦法直接匹配或是藉由重匹配加新的邊，
複雜度$\mathcal{O}(N^2)$。

AC Code

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#pragma pack(0)
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
#define pb(x) emplace_back(x)
#define MOD 1000000007
#define MOD2 998244353
#define _INFINITY 9223372036854775807
#define fast ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

int n, k, match[1005], ans, t = 0;
vector<int> adj[1005];
bool vis[1005];

bool bimatch(int x)
{
    for (int i : adj[x])
    {
        if (!vis[i])
        {
            vis[i] = 1;
            if (!match[i] || bimatch(match[i]))
            {
                match[i] = x;
                return 1;
            }
        }
    }
    return 0;
}

signed main()
{
    while (cin >> n >> k)
    {
        t++;
        if (n == 0 && k == 0)
            break;


        memset(match, 0, sizeof(match));
        ans = 0;
        for (int i = 1; i <= n; i++)
            adj[i].clear();



        for (int i = 1; i <= k; i++)
        {
            int x, y;
            cin >> x >> y;
            adj[x].pb(y);
        }
        for (int i = 1; i <= n; i++)
        {
            memset(vis, 0, sizeof(vis));
            if (bimatch(i))
                ans++;
        }
        cout << "Case #" << t << ":" << ans << '\n';
    }
}