bfs構(gòu)建層次圖
dfs找增廣路
線形規(guī)劃與網(wǎng)絡(luò)流24則-24.騎士共存問題
在一個n*n個方各的國際象棋棋盤上,馬可以攻擊的范圍如圖所示.棋盤上某些方各設(shè)置了障礙,騎士不得進入.
求,棋盤上最多可以放置多少個騎士,使得他們彼此互不攻擊.
數(shù)據(jù)范圍:1<=n<=200,0<=m<n^2
解:對棋盤染色,騎士的跳躍不同色,構(gòu)成2分圖,求最大獨立集.
最大獨立集=格子數(shù)(參與匹配)-最大匹配,即格子數(shù)-障礙數(shù)-最大匹配.
因為數(shù)據(jù)范圍過大,用km求最大匹配顯然tle了.于是用了dinic..第一次寫..還是仿寫的..
#include <iostream>
#include <fstream>
using namespace std;
#define INF 99999999
ifstream fin("flow.in");
ofstream fout("flow.out");
int h[8]=
{-1,-2,-2,-1,1,2,2,1};
int l[8]={-2,-1,1,2,2,1,-1,-2};
bool can[201][201];
int maxflow=0;
const int MAXN=200*200+2;
struct node
{
int x,y,c;
int op;
int next;
}p[MAXN*8*2+1];
int first[MAXN];
int level[MAXN],st[MAXN],t[MAXN],state[MAXN];
int count_=0;
void addedge(int a,int b,int c)
{
count_++;
p[count_].x=a,p[count_].y=b,p[count_].c=c;
p[count_].next=first[a];
p[count_].op=count_+1;first[a]=count_;
count_++;
p[count_].x=b,p[count_].y=a,p[count_].c=0;
p[count_].next=first[b];
p[count_].op=count_-1;first[b]=count_;
}
int N,M;
int S,T;
bool make_level()
{
int head,tail,i,j;
memset(level,-1,sizeof(level));
level[S]=0;
st[head=tail=0]=S;
while(head<=tail)
{
i=st[head++];
for (int v=first[i];v!=-1;v=p[v].next)
{
j=p[v].y;
if (p[v].c&&level[j]==-1)
{
level[j]=level[i]+1;
if (j==T) return true;
st[++tail]=j;
}
}
}
return false;
}
void dinic()
{
int i,j,delta,Stop;
st[Stop=1]=S;
for (int i=S;i<=T;i++)
{
t[i]=first[i];
}
while(Stop)
{
i=st[Stop];
if (i!=T)
{
while(t[i]!=-1)
{
if (p[t[i]].c&&level[i]+1==level[j=p[t[i]].y]) break;
t[i]=p[t[i]].next;
}
if (t[i]!=-1)
{
st[++Stop]=j;
state[Stop]=t[i];
}
else
{
Stop--;
level[i]=-1;
}
}
else
{
delta=INF;
for (i=Stop;i>=2;i--)
if (p[state[i]].c<delta) delta=p[state[i]].c;
maxflow+=delta;
for (i=Stop;i>=2;i--)
{
p[state[i]].c-=delta;
int op_=p[state[i]].op;
p[op_].c+=delta;
if (p[state[i]].c==0) Stop=i-1;
}
}
}
}
int main()
{
memset(can,true,sizeof(can));
memset(first,-1,sizeof(first));
fin>>N>>M;
for (int i=1;i<=M;i++)
{
int x,y;
fin>>x>>y;
can[x][y]=false;
}
S=0,T=N*N+1;
//for (int i=S;i<=T;i++)
//first[i]=-1;
for (int i=1;i<=N;i++)
{
for (int j=1;j<=N;j++)
{
if (!can[i][j]) continue;
if ((i+j)%2==0) {addedge(((i-1)*N+j),T,1);continue;}
int id1=((i-1)*N+j);
addedge(0,id1,1);
for (int k=0;k<8;k++)
{
int x,y;
x=i+h[k],y=j+l[k];
if (x<1||y<1||x>N||y>N) continue;
if (!can[x][y]) continue;
int id2=((x-1)*N+y);
addedge(id1,id2,INF);
}
}
}
while(make_level())
dinic();
fout<<N*N-M-maxflow<<endl;
system("pause");
return 0;
}