米斯兰达 @ 2018-12-20 18:37:43
蒟蒻求助qwq(T了8个,wa了两个,已经写成线性了为什么还是T了啊····)
#include<bits/stdc++.h>
using namespace std;
const int maxn=160000+5,jia[8]={-2,-2,-1,-1,1,1,2,2},jia1[8]={-1,1,-2,2,-2,2,-1,1};
bool Map[202][202],mark[maxn];
int Link[maxn],Next[maxn],cnt,End[maxn],Last[maxn];
queue<int> q;
bool Find(int x)
{
for (int i=Last[x];i;i=Next[i])
{
int j=End[i];
if (!mark[j])
{
mark[j]=true;
if (Link[j]==0||Find(Link[j]))
{
Link[j]=x;
return true;
}
}
}
}
void jian(int a,int b)
{
cnt++;
End[cnt]=b;
Next[cnt]=Last[a];
Last[a]=cnt;
}
int main()
{
//freopen("ceshi.in","r",stdin);
int n,m;
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{int a,b;scanf("%d%d",&a,&b);Map[a][b]=true;}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (!Map[i][j]&&(i+j)%2==0)
{
q.push(((i-1)*n+j-1)/2+1);
//这里就是标点啦,看不懂可以忽略掉emm
for (int k=0;k<=7;k++)
{
int x=i+jia[k];
int y=j+jia1[k];
if (Map[x][y]||x>n||x<1||y>n||y<1)
continue;
jian(((i-1)*n+j-1)/2+1,((x-1)*n+y-1)/2+1);
}
}
int tot=0;
while (q.size())
{
memset(mark,0,sizeof(mark));
if (Find(q.front())) tot++;
q.pop();
}
printf("%d",n*n-m-tot);
}
by RiverFun @ 2018-12-20 18:57:04
@米斯兰达 把mark数组开小一些
by 米斯兰达 @ 2018-12-20 19:07:49
@Steve_braveman mark开大开小不影响吧
by RiverFun @ 2018-12-20 19:23:37
@米斯兰达 memset很费时间的
by 米斯兰达 @ 2018-12-25 18:29:35
@Steve_braveman 谢谢大佬,但还是t了qwq,同时又wa了一个点,是代码不够优秀吗
by tuliwei @ 2019-01-31 09:37:44
数组开小了。
by tuliwei @ 2019-01-31 09:38:13
这题可能有720000条边