walk_alone @ 2018-10-30 20:55:27
感觉没什么问题
#include <cstdio>
#include <algorithm>
#include <queue>
#include <memory.h>
using namespace std;
const int maxn=999999999;
struct line
{
int from;
int to;
int v;
int next;
};
line que[400001];
int headers[40050],depth[40050],cnt,n;
bool book[201][201];
int nexto[8][2]={{1,2},
{2,1},
{2,-1},
{-1,2},
{1,-2},
{-2,1},
{-1,-2},
{-2,-1}};
int cal(int x,int y)
{
return n*(x-1)+y;
}
void add(int from,int to,int v)
{
que[cnt].from=from;
que[cnt].to=to;
que[cnt].v=v;
que[cnt].next=headers[from];
headers[from]=cnt;
cnt++;
}
bool bfs(int s,int t)
{
memset(depth,0,sizeof(depth));
queue<int>q;
q.push(s);
depth[s]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=headers[u];i!=-1;i=que[i].next)
if(!depth[que[i].to] && que[i].v>0)
{
depth[que[i].to]=depth[u]+1;
q.push(que[i].to);
}
}
return depth[t]!=0;
}
int dfs(int u,int t,int flow)
{
if(u==t || flow<=0)
return flow;
for(int i=headers[u];i!=-1;i=que[i].next)
if(depth[que[i].to]==depth[u]+1)
{
int d=dfs(que[i].to,t,min(flow,que[i].v));
if(d>0)
{
que[i].v-=d;
que[i^1].v+=d;
return d;
}
}
return 0;
}
int dinic(int s,int t)
{
int ans=0;
while(bfs(s,t))
while(int d=dfs(s,t,maxn))
ans+=d;
return ans;
}
int main()
{
int a,b,s=0,t,m;
scanf("%d%d",&n,&m);
t=n*n+1;
memset(headers,-1,sizeof(headers));
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
book[a][b]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(book[i][j])
continue;
if((i+j)&1)
{
add(s,cal(i,j),1);
add(cal(i,j),s,0);
for(int o=0;o<=7;o++)
{
int tx=i+nexto[o][0];
int ty=j+nexto[o][1];
if(tx<1 || ty<1 || tx>n || ty>n || book[tx][ty])
continue;
add(cal(i,j),cal(tx,ty),maxn);
add(cal(tx,ty),cal(i,j),0);
}
}
else
{
add(cal(i,j),t,1);
add(t,cal(i,j),0);
}
}
printf("%d",n*n-m-dinic(s,t));
return 0;
}
by Bobh @ 2018-10-30 20:56:07
%%%%%
by wuyuema @ 2018-10-30 20:56:11
%%%%%
by Brandon鹏 @ 2018-10-30 20:56:28
@walk_alone FYT大佬怎么可能有什么问题???
by wuyuema @ 2018-10-30 20:56:30
膜你
by wuyuema @ 2018-10-30 20:56:47
FYT:我这么弱
by walk_alone @ 2018-10-30 20:56:51
@Brandon鹏 哪有您神仙强
by Polaris1087 @ 2018-10-30 20:57:17
你们又开始了sro
by 追风の裙子桑 @ 2018-10-30 20:58:13
%%%