第一个点输出4也能ac嘛,太奇妙了
查看原帖
第一个点输出4也能ac嘛,太奇妙了
817442
Sakuya_maid楼主2023/4/19 16:33

这是我的代码:

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int N = 1e5 + 5;

int u;

int match[N];

int n, m, x, v;

LL now;

int st[N];

int h[N], ne[N], e[N], idx;

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

inline bool find(int x)
{
    for(int i = h[x]; ~i; i = ne[i])
    {
        int j = e[i];

        if(st[j] == now)continue;
        st[j] = now;

        if(match[j] == 0 || find(match[j]))
        {
            match[j] = x;
            return true;
        }
    }
    return false;
}

void solve()
{
    memset(h, -1, sizeof h);
    
    cin >> n >> m;

    for(int i = 1; i <= m; ++ i)
    {
        cin >> u >> v;
        v ++;
        u ++ ;
        add(u , v);
        // add(v , u);
    }

    LL res = 0;

    for(int i = 1; i <= n; ++ i)
    {
        now = i;
        if(find(i))res ++;
        // else if(!find(i)) break;
    }

    cout << n - res << '\n';

    
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // int T;
    // for (cin >> T; T -- ; )
        solve();

}
2023/4/19 16:33
加载中...