【网络流24题】骑士共存问题

刺骨的言语ヽ痛彻心扉 2021-12-03 14:39 237阅读 0赞

题面：

[https://www.luogu.org/problemnew/show/P3355][https_www.luogu.org_problemnew_show_P3355]

题解：

水题，染色+最小割。

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<vector>
    #include<queue>
    #define ri register int
    #define N 50000
    #define INF 1000000007
    #define S 0
    #define T (n*n+1)
    using namespace std;
    
    const int dx[]={-2,-2,-1,-1,1,1,2,2},dy[]={
        1,-1,2,-2,-2,2,1,-1};
    int n,m,x,y,g[250][250];
    
    struct graph {
      vector<int> to,w;
      vector<int> ed[N];
      int cur[N],d[N];
      void add_edge(int u,int v,int w1) {
        //cout<<u<<" "<<v<<" "<<w1<<endl;
        to.push_back(v); w.push_back(w1); ed[u].push_back(to.size()-1);
        to.push_back(u); w.push_back(0);  ed[v].push_back(to.size()-1);
      }
      bool bfs() {
        queue<int> q;
        memset(d,0x3f,sizeof(d));
        d[0]=0; q.push(0);
        while (!q.empty()) {
          int x=q.front(); q.pop();
          for (ri i=0,l=ed[x].size();i<l;i++) {
            int e=ed[x][i];
            if (w[e] && d[x]+1<d[to[e]]) {
              d[to[e]]=d[x]+1;
              q.push(to[e]);
            }
          }
        }
        return d[T]<INF;
      }
      int dfs(int x,int limit) {
        if (x==T || !limit) return limit;
        int tot=0;
        for (ri &i=cur[x];i<ed[x].size();i++) {
          int e=ed[x][i];
          if (d[to[e]]==d[x]+1 && w[e]) {
            int f=dfs(to[e],min(limit,w[e]));
            if (!f) continue;
            w[e]-=f; w[1^e]+=f; 
            tot+=f; limit-=f;
            if (!limit) return tot;
          }
        }
        return tot;
      }
      int dinic() {
        int ret=0;
        while (bfs()) {
          memset(cur,0,sizeof(cur));
          ret+=dfs(S,INF);
        }
        return ret;
      }
    } G;
    
    int main(){
      scanf("%d %d",&n,&m);
      for (ri i=1;i<=m;i++) {
        scanf("%d %d",&x,&y);
        g[x][y]=1;
      }
      int sum=0;
      for (ri i=1;i<=n;i++) 
        for (ri j=1;j<=n;j++) if (!g[i][j]) {
          sum++;
          if ((i+j)%2==0) {
            G.add_edge(S,n*(i-1)+j,1);
            for (ri k=0;k<8;k++) {
              int nx=i+dx[k],ny=j+dy[k];
              if (nx>=1 && nx<=n && ny>=1 && ny<=n && g[nx][ny]==0) G.add_edge(n*(i-1)+j,n*(nx-1)+ny,INF);
            }
          }
          else G.add_edge(n*(i-1)+j,T,1);
        }
      cout<<sum-G.dinic()<<endl;
    }

转载于:https://www.cnblogs.com/shxnb666/p/11183090.html

[https_www.luogu.org_problemnew_show_P3355]: https://www.luogu.org/problemnew/show/P3355