GoldenPotato137 @ 2018-01-29 12:20:36
RT,求dalao帮忙
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N=200+30;
const int inf=0x3f3f3f3f;
struct road
{
int w,to,opp;
};
vector <road> e[N*N];
bool mark[N][N];
int n,m,S=0,T=40960;
void AddLine(int s,int t,int w)
{
road temp;
temp.to=t,temp.w=w,temp.opp=e[t].size();
e[s].push_back(temp);
temp.to=s,temp.w=0,temp.opp=e[s].size()-1;
e[t].push_back(temp);
}
inline int GetNum(int y,int x)
{
return (y-1)*n+x;
}
int depth[N*N];
queue <int> q;
bool bfs()
{
memset(depth,0,sizeof depth);
q.push(S);
while(!q.empty())
{
int now=q.front(),size=e[now].size();
for(int i=0;i<size;i++)
if(depth[e[now][i].to]==0 and e[now][i].w>0 and e[now][i].to!=S)
{
depth[e[now][i].to]=depth[now]+1;
q.push(e[now][i].to);
}
q.pop();
}
return depth[T]==0?false:true;
}
int dfs(int now,int ans)
{
if(now==T or ans==0) return ans;
int size=e[now].size(),rec=0;
for(int i=0;i<size;i++)
if(e[now][i].w>0 and depth[e[now][i].to]==depth[now]+1)
{
int to=e[now][i].to,t_ans=dfs(to,min(ans-rec,e[now][i].w));
e[now][i].w-=t_ans;
e[to][e[now][i].opp].w+=t_ans;
rec+=t_ans;
if(rec==ans) break;
}
return rec;
}
int Dinic()
{
int ans=0;
while(bfs())
ans+=dfs(S,inf);
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<=n*n;i++)
e[i].reserve(16);
for(int i=1;i<=m;i++)
{
int tx,ty;
scanf("%d%d",&tx,&ty);
mark[ty][tx]=true;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(!mark[i][j])
{
int now=(i-1)*n+j;
if((i%2)==(j%2))//R
AddLine(S,now,1);
else //Y
AddLine(now,T,1);
if((i%2)!=(j%2)) continue;
if(i-2>0 and j-1>0 and !mark[i-2][j-1]) AddLine(now,GetNum(i-2,j-1),inf);
if(i-2>0 and j+1<=n and !mark[i-2][j+1]) AddLine(now,GetNum(i-2,j+1),inf);
if(i-1>0 and j-2>0 and !mark[i-1][j-2]) AddLine(now,GetNum(i-1,j-2),inf);
if(i-1>0 and j+2<=n and !mark[i-1][j+2]) AddLine(now,GetNum(i-1,j+2),inf);
if(i+1<=n and j-2>0 and !mark[i+1][j-2]) AddLine(now,GetNum(i+1,j-2),inf);
if(i+1<=n and j+2<=n and !mark[i+1][j+2]) AddLine(now,GetNum(i+1,j+2),inf);
if(i+2<=n and j-1>0 and !mark[i+2][j-1]) AddLine(now,GetNum(i+2,j-1),inf);
if(i+2<=n and j+1<=n and !mark[i+2][j+1]) AddLine(now,GetNum(i+2,j+1),inf);
}
printf("%d",n*n-m-Dinic());
return 0;
}
by sermoon @ 2018-01-29 12:29:40
网络流跑太慢了。。。。。
用Dinic优化或者ISAP吧