求助!!P3355 骑士共存问题
  • 板块灌水区
  • 楼主Y_F_k_
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/10/20 21:05
  • 上次更新2023/11/5 10:17:22
查看原帖
求助!!P3355 骑士共存问题
145577
Y_F_k_楼主2020/10/20 21:05

请问这道题是卡匈牙利吗?

请问那位大佬能帮忙卡卡常?

# pragma optimize O(2)
# pragma optimize O(3)
# pragma optimize O(fast)
#include<bits/stdc++.h>

using namespace std;
int n,m,ans,tp,r;
int tot;
int sum[40020];
bool p[220][220];
bool q[220][220];
int dx[4]={1,2,2,1};
int dy[4]={2,1,-1,-2};
bool vis[40020];
int match[40020];
vector<int >g[40020];
int read()
{
    char ch=getchar();
    int s=0,w=1;
    while (ch<'0'||ch>'9')
    {
        if (ch=='-')
        {
            w=-1;
        }
        ch=getchar();
    }
    while (ch>='0'&&ch<='9')
    {
        s=(s<<1)+(s<<3)+ch-'0';
        ch=getchar();
    }
    return s*w;
}
bool Hungarian(int u)
{
    for (int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if (!vis[v])
        {
            vis[v]=1;
            if (!match[v]||Hungarian(match[v])==1)
            {
                match[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
int tra(int x,int y)
{
    return (x-1)*n+y;
}
int main()
{
    n=read(),m=read();
    for (int i=1;i<=m;i++)
    {
        int a,b;
        a=read(),b=read();
        p[a][b]=1;
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            if (!p[i][j])
            {
                r++;
                for (int o=0;o<4;o++)
                {
                    if (i+dx[o]>=1&&i+dx[o]<=n&&j+dy[o]>=1&&j+dy[o]<=n&&!p[i+dx[o]][j+dy[o]])
                    {
                        g[tra(i,j)].push_back(tra(i+dx[o],j+dy[o]));
                        g[tra(i+dx[o],j+dy[o])].push_back(tra(i,j));
                    }
                }
                if ((i+j)%2==1) 
                {
                    sum[++tot]=tra(i,j);
                }
            }
        }
    }
    for (int i=1;i<=tot;i++)
    {
        memset(vis,0,sizeof(vis));
        if (Hungarian(sum[i])==1) ans++;
    }
    cout<<r-ans<<endl;
    return 0;
}
2020/10/20 21:05
加载中...