洛谷 P3355 骑士共存问题-白红宇

洛谷 P3355 骑士共存问题

阅读量：5359 次

发布时间：2019-06-15

本文共 2212 字，大约阅读时间需要 7 分钟。

题意：给你一个棋盘，然后有一个骑士rider，棋盘上有一些障碍，问你最多放多少个骑士

思路：期初我一直以为这种题是什么八皇后问题的变形，队友告诉我，这是网络流，由于这道题的黄色格子上的棋子的下一步总是调到红色格子上，所以我们把所有的红色格子连到一个超级源上，所有的黄色格子连接到一个超级汇上，然后对于每个可以跳到的位置我们在建立一条边，容量为1 ，因为我们最后求的是这张图的最小割，而最小割定理我们知道，最小割其实就是图的最大流，之前的板子可能出了一点点问题，不在用了，总是TLE，不知道为什么，很玄学（玄不救非，氪不改命！！）

代码:

#include 
     
      #include 
      #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #define zero(a) fabs(a)
                 
                  y?x:y;};int min(int x,int y){ return x
                  
                   '9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}using namespace std;struct Edge{ int next,to,f;};struct Dinic{ int s,t; Edge e[1000010]; int cnt=2,head[1000010]={ 0}; int dis[1000010]={ 0}; Dinic (){} void init(int _s,int _t) { s=_s,t=_t; } void addedge(int u,int v,int f) { e[cnt]={head[u],v,f}; head[u]=cnt++; e[cnt]={head[v],u,0}; head[v]=cnt++; } bool bfs() { memset(dis,0,sizeof(dis)); dis[s]=1; queue
                   
                     q; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(!dis[v]&&e[i].f>0) { dis[v]=dis[u]+1; q.push(v); } } } return dis[t]!=0; } int dfs(int u,int flow) { if(u==t||flow==0) return flow; int flow_sum=0; for(int i=head[u];i;i=e[i].next) { int v=e[i].to,f=e[i].f; if(dis[v]!=dis[u]+1||f==0) continue; int temp=dfs(v,min(flow-flow_sum,f)); e[i].f-=temp; e[i^1].f+=temp; flow_sum+=temp; if(flow_sum>=flow) break; } if(!flow_sum) dis[u]=-1; return flow_sum; } int maxflow() { int ans=0; while(bfs()) { while(int temp=dfs(s,INF)) ans+=temp; } return ans; }}DC;#define id(x,y) ((x-1)*n+y)bool mp[210][210];int main(){ int n,m; n=read(),m=read(); int t=n*n+1; int s=0; DC.init(s,t); for(int i=1;i<=m;i++){ int p,q; p=read(),q=read(); mp[p][q]=1; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(mp[i][j])continue; if((i+j)%2){ DC.addedge(DC.s,id(i,j),1); for(int k=0;k<8;k++){ int p=i+dir[k][0]; int q=j+dir[k][1]; if(p<1||p>n||q<1||q>n||mp[p][q]) continue; DC.addedge(id(i,j),id(p,q),inf); } } else{ DC.addedge(id(i,j),DC.t,1); } } } int ans=DC.maxflow(); printf("%d\n",n*n-m-ans); return 0;}

转载于:https://www.cnblogs.com/lalalatianlalu/p/9055059.html

你可能感兴趣的文章