π酱 @ 2019-07-11 22:18:06
我已经改了2个多小时了,就是找不出来错误QAQ
求大佬帮忙
#include<bits/stdc++.h>
#define Inf 0x7fffffff
using namespace std;
queue<int> Q;
int Ht[9]= {0,-2,-2,-1,-1,1,1,2,2};
int Lt[9]= {0,1,-1,2,-2,2,-2,1,-1};
int a,b,x,X,Y,n,m,New,B,W,Black,White,Start,End,Cnt,Used,Ans,Head[40010],Cur[40010],Dep[40010],To[400010],Next[400010],Val[00010],Map[210][210],Id[210][210];
template<typename T>
int Read(T &x) {
x=0;
int f=1;
char c=getchar();
while(c!='-'&&!isdigit(c)) {
c=getchar();
}
while(!isdigit(c)) {
if(c=='-') {
f=-f;
}
c=getchar();
}
while(isdigit(c)) {
x=x*10+c-'0';
c=getchar();
}
x*=f;
if(c=='\n') {
return 1;
} else {
return 0;
}
}
void Write(long long x) {
if(x<0) {
putchar('-');
x=-x;
}
if(x>9) {
Write(x/10);
}
putchar(x%10+'0');
}
inline int Num(int x,int y) {
return (x-1)*n+y;
}
inline void Add(int a,int b,int x) {
To[++Cnt]=b;
Next[Cnt]=Head[a];
Head[a]=Cnt;
Val[Cnt]=x;
To[++Cnt]=a;
Next[Cnt]=Head[b];
Head[b]=Cnt;
Val[Cnt]=0;
}
bool Bfs() {
memset(Dep,-1,sizeof(Dep));
Dep[Start]=0;
Q.push(Start);
while(!Q.empty()) {
x=Q.front();
Q.pop();
for(int i=Head[x]; i; i=Next[i]) {
if(Val[i]&&Dep[To[i]]==-1) {
Dep[To[i]]=Dep[x]+1;
Q.push(To[i]);
}
}
}
return Dep[End]!=-1;
}
int Dfs(int x,int f) {
int w=0,Used=0;
if(x==End) {
return f;
}
for(int i=Cur[x]; i; i=Next[i]) {
if(Dep[To[i]]==Dep[x]+1) {
w=f-Used;
w=Dfs(To[i],min(Val[i],w));
Val[i]-=w;
if(Val[i]) {
Cur[x]=i;
}
Val[i^1]+=w;
Used+=w;
if(Used==f) {
return f;
}
}
}
if(!Used) {
Dep[x]=-1;
}
return Used;
}
void Dinic() {
while(Bfs()) {
for(int i=1; i<=n*n+5; i++) {
Cur[i]=Head[i];
}
Ans+=Dfs(Start,Inf);
}
}
int main() {
Ans=0;
Cnt=1;
Read(n);
Read(m);
for(int i=1; i<=m; i++) {
Read(X);
Read(Y);
Map[X][Y]=1;
}
Start=n*n+1;
End=n*n+2;
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(Map[i][j]) {
continue;
}
if((i+j)&1) {
Add(Start,Num(i,j),1);
for(int k=1; k<=8; k++) {
X=i+Ht[k];
Y=j+Lt[k];
if((X>n)||(X<1)||(Y<1)||(Y>n)||(Map[X][Y])) {
continue;
}
Add(Num(i,j),Num(X,Y),Inf);
}
}
else {
Add(Num(i,j),End,1);
}
}
}
Dinic();
Write(n*n-Ans-m);
return 0;
}
by π酱 @ 2019-07-11 22:43:35
已解决,我傻逼了QAQ