洛谷P4304 [TJOI2013]攻击装置 题解

题目链接：

https://www.luogu.org/problemnew/show/P4304

分析：

最大独立集

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

独立集：点集，图中选一堆点，这堆点两两之间没有连边

最大独立集：尽可能多得选点，使得其满足独立集的性质

这是网络流二分图经典题目，值得练习

代码：

#include<cstdio>

#include<utility>

#include<vector>

using namespace std;

int x[9]={0,-1,-2,1,2,-1,-2,1,2};

int y[9]={0,-2,-1,-2,-1,2,1,2,1};

struct ben

{

    int first,second;

};

vector<ben> v[205][205];

int a[205][205];

ben link[205][205];

int vis[205][205];

int t;

bool find(ben andd)

{

    int x=andd.first;

    int y=andd.second;

    for(int i=0;i<v[x][y].size();i++)

    {

        int p=v[x][y][i].first;

        int q=v[x][y][i].second;

        if(vis[p][q]!=t)

        {

            vis[p][q]=t;

            int ls=link[p][q].first;

            int ls2=link[p][q].second;

            if((ls==0&&ls2==0)||find(link[p][q]))

            {

                link[p][q].first=x;

                link[p][q].second=y;

                return 1;

            }

        }

    }

    return 0;

}

int main()

{

    int n;

    scanf("%d",&n);

    int ans=0;

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

    {

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

        {

            scanf("%1d",&a[i][j]);

            if(a[i][j]==0)

            ans++;

        }

    }

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

    {

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

        {

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

            {

                int xx=i+x[k];

                int yy=j+y[k];

                if(xx<=0||xx>n||yy<=0||yy>n)

                continue;

                ben tmp;

                tmp.first=xx;

                tmp.second=yy;

                if(a[xx][yy]==0)

                {

                    v[i][j].push_back(tmp);

                }

            }

        }

    }

    int cnt=0;

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

    {

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

        {

            if(a[i][j]==1)

            continue;

            t++;

            ben tmp;

            tmp.first=i;

            tmp.second=j;

            if(find(tmp))

            {

                cnt++;

            }

            //else

            //break;

        }

    }

    printf("%d\n",ans-cnt/2);

    return 0;

}