此题卡匈牙利？

__gcd @ 2020-03-22 20:12:20

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define endl '\n'
using namespace std;

inline int read()
{
    char c = getchar();
    int x = 0; bool op = 0;
    while(!isdigit(c))op |= (c == '-'), c = getchar();
    while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return op ? -x : x;
}

const int N = 210;
const int V = N * N;
const int E = V * 8;
const int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
const int dy[8] = {2, 1, -1, -2, 2, 1, -1, -2};

int n, m, tot = 0;
int a[N][N], id[N][N], head[V], to[E], nxt[E], match[V];
bool vis[V];

inline void addedge(int u, int v)
{
    to[++tot] = v;
    nxt[tot] = head[u];
    head[u] = tot;
    return ;
}

bool dfs(int u)
{
    for(register int i = head[u]; i; i = nxt[i])
    {
        if(vis[to[i]] == true)
            continue;
        vis[to[i]] = true;
        if(match[to[i]] == 0 || dfs(match[to[i]]) == true)
        {
            match[to[i]] = u;
            return true;
        }
    }
    return false;
}

int main()
{
    n = read(); m = read();
    for(register int i = 1; i <= m; ++i)
    {
        int x = read(), y = read();
        a[x][y] = true;
    }
    int cnt = 0;
    for(register int i = 1; i <= n; ++i)
    {
        for(register int j = 1; j <= n; ++j)
        {
            if((i + j) % 2 == 1)
                id[i][j] = ++cnt;
        }
    }
    int left = cnt;
    for(register int i = 1; i <= n; ++i)
    {
        for(register int j = 1; j <= n; ++j)
        {
            if((i + j) % 2 == 0)
                id[i][j] = ++cnt;
        }
    }
    for(register int i = 1; i <= n; ++i)
    {
        for(register int j = 1; j <= n; ++j)
        {
            if((i + j) % 2 == 0 || a[i][j] == true)
                continue;
            for(register int dir = 0; dir < 8; ++dir)
            {
                int nx = i + dx[dir], ny = j + dy[dir];
                if(nx < 1 || nx > n || ny < 1 || ny > n || a[nx][ny] == true)
                    continue;
                addedge(id[i][j], id[nx][ny]);
            }
        }
    }
    int ans = 0;
    for(register int i = 1; i <= left; ++i)
    {
        memset(vis, false, sizeof(vis));
        if(dfs(i) == true)
            ans++;
    }
    cout << n * n - ans - m;
    return 0;
}

by PrincessQi @ 2020-03-22 20:15:16

不知道，我用的Dinic

by ♘GoldHookDream♞ @ 2020-03-22 20:25:16

@一只大头 V改成15000试试

by __gcd @ 2020-03-22 20:27:20

@eason0511 亲测RE+WA

by Smile_Cindy @ 2020-03-22 20:48:18

@一只大头 我的匈牙利，拿着看看吧……

#include <bits/stdc++.h>
using namespace std;
const int dx[]={-2,-1,1,2,2,1,-1,-2};
const int dy[]={1,2,2,1,-1,-2,-2,-1};
const int MAX_N=205;
int tot[2],A[MAX_N][MAX_N];
bool ok[MAX_N][MAX_N];
int n,m;
vector<int> g[MAX_N*MAX_N/2];
bool used[MAX_N*MAX_N/2];
int match[MAX_N*MAX_N/2];
bool dfs(int v)
{
    used[v]=true;
    for(int i=0;i<g[v].size();i++)
    {
        int to=g[v][i];
        if(match[to]==-1 || !used[match[to]] && dfs(match[to]))
        {
            match[to]=v;
            return true;
        }
    }
    return false;
}
int bipartite_matching()
{
    memset(match,-1,sizeof(match));
    int ret=0;
    for(int i=tot[1];i>=1;i--)
    {
        memset(used,false,sizeof(used));
        ret+=dfs(i);
    }
    return ret;
}
bool in(int x,int y)
{
    return x>0 && x<=n && y>0 && y<=n;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            ok[i][j]=true;
        }
    }
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        ok[x][y]=false;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(!ok[i][j])continue;
            A[i][j]=++tot[(i+j)%2];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(A[i][j] && (i+j)%2)
            {
                for(int k=0;k<8;k++)
                {
                    int x=i+dx[k],y=j+dy[k];
                    if(in(x,y) && A[x][y])g[A[i][j]].push_back(A[x][y]);
                }
            }
        }
    }
    cout<<tot[0]+tot[1]-bipartite_matching()<<endl;
    return 0;
}

by __gcd @ 2020-03-22 20:48:39

@Alpha thx

by Smile_Cindy @ 2020-03-22 21:15:28

忘了说，虽然匈牙利的复杂度为 O(nm) 理论上不可通过本题，但是常数小得奇怪的匈牙利还是在一通优化之后通过了本题。

by 杨氏之子 @ 2020-03-22 22:03:46

@一只大头

#include<bits/stdc++.h>
using namespace std;

const int dx[8]={1,2,2,1,-1,-2,-2,-1};
const int dy[8]={-2,-1,1,2,-2,-1,1,2};

int n,m,match[40010],ans;
bool vis[40010],bj[210][210];
vector<int> nbr[40010];

bool dfs(int x){
    for(int i=0;i<nbr[x].size();i++){
        int y=nbr[x][i];
        if(vis[y]==0){
            vis[y]=1;
            if(match[y]==0||dfs(match[y])==1){
                match[y]=x;
                return 1;
            }
        }
    }
    return 0;
}

int get(int x,int y){
    return (x-1)*n+y;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        bj[x][y]=1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if((i+j)%2||bj[i][j])
                continue;
            for(int k=0;k<8;k++){
                int nx=i+dx[k],ny=j+dy[k];
                if(nx>0&&ny>0&&nx<=n&&ny<=n&&bj[nx][ny]==0)
                    nbr[get(i,j)].push_back(get(nx,ny));
            }
        }
    for(int i=1;i<=n*n;i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i))
            ans++;
    }
    cout<<n*n-ans-m;
    return 0;
}