AThousandSuns @ 2018-12-14 19:29:43
这是代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PB push_back
#define MP make_pair
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
char ch=getchar();int x=0,f=0;
while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
const int d[8][2]={{1,-2},{1,2},{2,-1},{2,1},{-1,-2},{-1,2},{-2,-1},{-2,1}};
int n,m,s,t,el=1,head[44444],cur[44444],to[1444444],flow[1444444],nxt[1444444],dis[44444],q[44444],h,r;
bool block[222][222],vis[222][222];
inline void add(int u,int v,int w){
if(vis[u][v]) return;vis[u][v]=true;
to[++el]=v;flow[el]=w;nxt[el]=head[u];head[u]=el;
to[++el]=u;flow[el]=0;nxt[el]=head[v];head[v]=el;
}
bool bfs(){
MEM(dis,-1);
dis[q[h=r=1]=s]=0;
while(h<=r){
int u=q[h++];
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(~dis[v] || !flow[i]) continue;
dis[q[++r]=v]=dis[u]+1;
}
}
return ~dis[t];
}
int dfs(int u,int minres){
if(u==t || !minres) return minres;
int f,rtf=0;
for(int &i=cur[u];i;i=nxt[i]){
int v=to[i];
if(dis[v]==dis[u]+1 && (f=dfs(v,min(minres,flow[i])))){
flow[i]-=f;
flow[i^1]+=f;
rtf+=f;
minres-=f;
if(!minres) break;
}
}
if(!minres) dis[u]=-1;
return rtf;
}
int dinic(){
int flow=0;
while(bfs()){
FOR(i,1,n*n+2) cur[i]=head[i];
flow+=dfs(s,1e9);
}
return flow;
}
int main(){
n=read();m=read();
FOR(i,1,m){
int x=read(),y=read();
block[x][y]=true;
}
FOR(i,1,n)
FOR(j,1,n){
if(block[i][j]) continue;
FOR(k,0,7){
int x=i+d[k][0],y=j+d[k][1];
if(x<1 || x>n || y<1 || y>n || block[x][y]) continue;
if((i+j)&1) add((i-1)*n+j,(x-1)*n+y,1);
else add((x-1)*n+y,(i-1)*n+j,1);
}
}
s=n*n+1;t=n*n+2;
FOR(i,1,n)
FOR(j,1,n){
if(block[i][j]) continue;
if((i+j)&1) add(s,(i-1)*n+j,1);
else add((i-1)*n+j,t,1);
}
printf("%d\n",n*n-m-dinic());
}
然后我发现输入46 0时,nxt[4448]变成了一个很大的数(1.6*10^7)!
我试着在add中加入
if(el==4448) printf("nxt[4448]=%d\n",nxt[4448]);
结果又输出了"nxt[4448]=0",但是bfs时nxt[4448]还是1.6*10^7!
帮忙看一下吧……调不出了……
by VenusM1nT @ 2018-12-14 19:39:31
@AThousandSuns 你在add
函数里输出一下u
和v
的值,再看看你开的vis
数组你就知道问题了
by VenusM1nT @ 2018-12-14 19:40:11
我又要说那句话了
十年OI一场空,__________
by VenusM1nT @ 2018-12-14 19:40:48
我用你的代码连建模部分都跑不过去……
by AThousandSuns @ 2018-12-14 19:41:36
@Venus 妈呀,居然犯了这种错……
谢谢大佬~
by VenusM1nT @ 2018-12-14 19:44:54
@AThousandSuns 你数组咋开那么小啊……我做网络流题的原则都是在不MLE的前提下开到3~10倍……
by AThousandSuns @ 2018-12-14 19:46:15
@Venus 我是严格按照最坏情况开的……经过计算的……
果然不是边的就没注意
by VenusM1nT @ 2018-12-14 19:50:38
@AThousandSuns Orz