巢穴

about:blank

dinic

bfs构建层次图
dfs找增广路
线形规划与网络流24则-24.骑士共存问题

在一个n*n个方各的国际象棋棋盘上,马可以攻击的范围如图所示.棋盘上某些方各设置了障碍,骑士不得进入.
求,棋盘上最多可以放置多少个骑士,使得他们彼此互不攻击.

数据范围:1<=n<=200,0<=m<n^2

解:对棋盘染色,骑士的跳跃不同色,构成2分图,求最大独立集.
最大独立集=格子数(参与匹配)-最大匹配,即格子数-障碍数-最大匹配.
因为数据范围过大,用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;
}

posted on 2009-11-10 21:34 Vincent 阅读(681) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理