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 _Herobrine_ @ 2020-03-30 18:39:27
前排Orz大佬
by xiaoyaowudi @ 2020-03-30 18:40:09
点数超了吧
by xiaoyaowudi @ 2020-03-30 18:41:19
4e4个点
by cz2009 @ 2020-03-30 18:41:27
让kkk来解决
by do_while_false @ 2020-03-30 18:44:47
求助kkk
by Scherzo @ 2020-03-30 18:49:54
标题党,jbl
by Flandre_495 @ 2020-03-30 18:51:21
送您表情/kk/kk/kk/kk/kk/kk/kk/kk
by UnyieldingTrilobite @ 2020-03-30 19:11:05
惊现CSPS400+!
by metaphysis @ 2020-03-30 19:55:19
@Roden
您能解释一下您建立流网络的逻辑吗?从代码来看似乎有些奇怪。
by Roden @ 2020-03-30 20:33:47
@metaphysis
奇数点:原点(0)向其连一条1边,向能踩到的偶数点连INF边。
偶数点:向汇点连边。
貌似没问题