BZOJ3175:[TJOI2013]攻击装置(二分图最大独立集)

Description

给定一个01矩阵，其中你可以在0的位置放置攻击装置。每一个攻击装置（x,y）都可以按照“日”字攻击其周围的 8个位置（x-1,y-2）,(x-2,y-1),(x+1,y-2),(x+2,y-1),(x-1,y+2),(x-2,y+1), (x+1,y+2),(x+2,y+1)
求在装置互不攻击的情况下，最多可以放置多少个装置。

Input

第一行一个整数N，表示矩阵大小为N*N。接下来N行每一行一个长度N的01串，表示矩阵。

Output

一个整数，表示在装置互不攻击的情况下最多可以放置多少个装置。

Sample Input

3
010
000
100

Sample Output

HINT

100%数据 N<=200

Solution

数组咋又双叒叕开小了……不过竟然还有90 数据良心(划掉)
第一眼读完题：这咋和炮兵阵地这么像，状压没跑了！
为了验证点击题解：网络流
emmm……我好像傻了这不就是骑士共存么= =……
裸的二分图最大独立集啊QAQ

Code

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<queue>

 #define M (1000000+10)

 #define N (40000+10)

 #define id(x,y) (x-1)*n+y

 using namespace std;

 struct node

 {

     int Flow;

     int next;

     int to;

 } edge[M*];

 int Depth[N];

 int head[N],num_edge,cnt;

 int n,m,s,e,x,y,INF,a[][],color[][];

 int dx[]= {,-,-,+,+,-,-,+,+};

 int dy[]= {,-,-,-,-,+,+,+,+};

 char st[N];

 queue<int>q;

 void add(int u,int v,int l)

 {

     edge[++num_edge].to=v;

     edge[num_edge].Flow=l;

     edge[num_edge].next=head[u];

     head[u]=num_edge;

 }

 bool Bfs(int s,int e)

 {

     memset(Depth,,sizeof(Depth));

     q.push(s);

     Depth[s]=;

     while (!q.empty())

     {

         int x=q.front();

         q.pop();

         for (int i=head[x]; i!=; i=edge[i].next)

             if (!Depth[edge[i].to] && edge[i].Flow>)

             {

                 Depth[edge[i].to]=Depth[x]+;

                 q.push(edge[i].to);

             }

     }

     return Depth[e];

 }

 int Dfs(int x,int low)

 {

     int Min,f=;

     if (x==e || low==)

         return low;

     for (int i=head[x]; i!=; i=edge[i].next)

         if (edge[i].Flow> && Depth[edge[i].to]==Depth[x]+ && (Min=Dfs(edge[i].to,min(low,edge[i].Flow))))

         {

             edge[i].Flow-=Min;

             edge[((i-)^)+].Flow+=Min;

             low-=Min;

             f+=Min;

             if (low==) return f;

         }

     if (!f) Depth[x]=-;

     return f;

 }

 int Dinic(int s,int e)

 {

     int Ans=;

     while (Bfs(s,e))

         Ans+=Dfs(s,0x7fffffff);

     return Ans;

 }

 int main()

 {

     scanf("%d",&n);

     s=,e=*+;

     for (int i=; i<=n; ++i)

     {

         scanf("%s",st);

         for (int j=; j<=n; ++j)

         {

             a[i][j]=st[j-]-'';

             color[i][j]=(i+j)%;

             if (a[i][j]==) continue;

             cnt++;

             if (color[i][j]==) add(s,id(i,j),), add(id(i,j),s,);

             else add(id(i,j),e,), add(e,id(i,j),);

         }

     }

     for (int i=; i<=n; ++i)

         for (int j=; j<=n; ++j)

         {

             if (a[i][j]== || color[i][j]==) continue;

             for (int k=; k<=; ++k)

             {

                 int x=i+dx[k],y=j+dy[k];

                 if (x< || x>n || y< || y>n || a[x][y]==) continue;

                 add(id(i,j),id(x,y),);

                 add(id(x,y),id(i,j),);

             }

         }

     printf("%d",cnt-Dinic(s,e));

 }

秒客网