求助!!P3355 骑士共存问题
  • 板块学术版
  • 楼主Y_F_k_
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/10/20 21:04
  • 上次更新2023/11/5 10:17:26
查看原帖
求助!!P3355 骑士共存问题
145577
Y_F_k_楼主2020/10/20 21:04

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

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

# 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:04
加载中...