Roden @ 2020-03-30 18:38:15
最大流部分没问题,应该是建模错了,但不知道哪里错了。导致MSVC、G++的结果都不一样。
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
#define MAX_V 10010
struct edge{int to,cap,rev;};
vector<edge> G[MAX_V];
void addedge(int from,int to,int cap)
{
G[from].push_back(edge{to,cap,(int)G[to].size()});
G[to].push_back(edge{from,0,(int)G[from].size()-1});
}
int level[MAX_V],iter[MAX_V];
int dfs(int v,int t,int f)
{
if(v==t)return f;
for(int &i=iter[v];i<G[v].size();i++)
{
edge &e=G[v][i];
if(e.cap>0&&level[v]<level[e.to])
{
int d=dfs(e.to,t,min(e.cap,f));
if(d>0){
e.cap-=d;
G[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int max_flow(int s,int t)
{
int flow=0;
queue<int> que;
Label:
memset(level,-1,sizeof(level));
level[s]=0;
que.push(s);
while(!que.empty())
{
int v=que.front();que.pop();
for(edge &e:G[v]){
if(e.cap>0&&level[e.to]<0){
level[e.to]=level[v]+1;
que.push(e.to);
}
}
}
if(level[t]<0)return flow;
memset(iter,0,sizeof(iter));
int f;
while((f=dfs(s,t,INF))>0)
flow+=f;
goto Label;
}
bool can[211][211];
const int dx[8]={1,1,-1,-1,2,2,-2,-2},dy[8]={2,-2,2,-2,1,-1,1,-1};
int main()
{
#ifndef ONLINE_JUDGE
freopen("stdin.txt", "r", stdin);
#endif
int n,m;
scanf("%d%d",&n,&m);
const int s=0,t=n*n+1;
for(int i=0;i<m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
can[x][y]=true;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(can[i][j])continue;
int index=i*n+j-n;
if((i+j)&1){
addedge(0,index,1);
for(int k=0;k<8;k++)
{
int x=i+dx[i],y=j+dy[i];
if(x>0&&x<=n&&y>0&&y<=n&&!can[x][y])
addedge(index,x*n+y-n,INF);
}
}else addedge(index,t,1);
}
printf("%d",n*n-m-max_flow(0,t));
return 0;
}
by metaphysis @ 2020-03-30 22:48:29
@Roden
哎呀,一个低级错误啊!
int x=i+dx[i],y=j+dy[i];
by metaphysis @ 2020-03-30 23:50:10
@Roden
还有一个小问题,题目约束中n<=200,则应:
#define MAX_V 40010
较为妥当。
此外,建议您使用链式前向星来表示图,然后重新编写Dinic算法的实现,尽量清晰一些,以便作为自己的标准代码库使用。使用邻接表来表示图的实现看起来似乎有些别扭。