【最大独立集】BZOJ3175- [Tjoi2013]攻击装置

【题目大意】

给定一个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)。
求在装置互不攻击的情况下，最多可以放置多少个装置。

【思路】

最大独立集=总点数-最大二分图匹配

我们都知道最大独立集一般用在二分图里…所以把每个点看作两个点，一个是从它出发，一个是抵达它。实际操作的时候因为会连正反边，不需要进行拆点。最大独立集=总点数-最大二分图匹配/2。

 #include<bits/stdc++.h>

 using namespace std;

 const int MAXN=;

 int n,maps[MAXN][MAXN];

 int lk[MAXN*MAXN],vis[MAXN*MAXN];

 vector<int> E[MAXN*MAXN];

 int check(int x,int y)

 {

     if (x>= && x<=n && y>= && y<=n && maps[x][y]) return ;else return ;

 }

 int id(int x,int y){return ((x-)*n+y);}

 void addedge(int u,int v)

 {

     E[u].push_back(v);

 }

 int find(int u)

 {

     for (int i=E[u].size()-;i>=;i--)

     {

         int v=E[u][i];

         if (!vis[v])

         {

             vis[v]=;

             if (!lk[v]|| find(lk[v]))

             {

                 lk[v]=u;

                 return ;

             }

         }

     }

     return ;

 }

 void init()

 {

     scanf("%d",&n);

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

     {

         char str[MAXN];

         scanf("%s",str);

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

             if (str[j]=='') maps[i][j+]=;else maps[i][j+]=;

     }

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

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

             if (maps[i][j]==)

             {

                 if (check(i-,j-)) addedge(id(i,j),id(i-,j-));

                 if (check(i-,j-)) addedge(id(i,j),id(i-,j-));

                 if (check(i+,j-)) addedge(id(i,j),id(i+,j-));

                 if (check(i+,j-)) addedge(id(i,j),id(i+,j-));

                 if (check(i-,j+)) addedge(id(i,j),id(i-,j+));

                 if (check(i-,j+)) addedge(id(i,j),id(i-,j+));

                 if (check(i+,j+)) addedge(id(i,j),id(i+,j+));

                 if (check(i+,j+)) addedge(id(i,j),id(i+,j+));

             }

 }

 void solve()

 {

     memset(lk,,sizeof(lk));

     int sum=,ans=;

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

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

         {

             if (maps[i][j]==)

             {

                 int x=id(i,j);

                 memset(vis,,sizeof(vis));

                 sum++;

                 if (find(x)) ans++;

             }

         }

     printf("%d",sum-ans/);//不要忘记了除以2

 }

 int main()

 {

     init();

     solve();

 }

巴特西

【最大独立集】BZOJ3175- [Tjoi2013]攻击装置

最新文章

热门文章