洛谷 - P5030 - 长脖子鹿放置 - 二分图最大独立集

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

写的第一道黑色题,图建对了.

隐约觉得互相攻击要连边,规定从奇数行流向偶数行.

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

因为把最大匹配d从顶点总数n中去掉,有n-2d个点.

从被去掉的点中,每个匹配重新加一个回来,加了d个.

所求为n-d.

估计顶点上限,40000+2

然后每个顶点最多连出8条边(其实只有奇数行连出)

每个顶点要么连源要么连汇

留出反向边的位置.

#include<bits/stdc++.h>

using namespace std;

#define ll long long

/* dinic begin */

const int MAXN=50000;

const int MAXM=1200000;

//注意网络流要预留反向边

const int INF=0x3f3f3f3f;

struct Edge{

    int to,next,cap,flow;

}edge[MAXM];

int tol;

int head[MAXN];

void init(){

    tol=2;

    memset(head,-1,sizeof(head));

}

void addedge(int u,int v,int w=1,int rw=0){

    edge[tol].to=v;edge[tol].cap=w;edge[tol].flow=0;

    edge[tol].next=head[u];head[u]=tol++;

    edge[tol].to=u;edge[tol].cap=rw;edge[tol].flow=0;

    edge[tol].next=head[v];head[v]=tol++;

}

int Q[MAXN];

int dep[MAXN],cur[MAXN],sta[MAXN];

bool bfs(int s,int t,int n){

    int front=0,tail=0;

    memset(dep,-1,sizeof(dep[0])*(n+1));

    dep[s]=0;

    Q[tail++]=s;

    while(front<tail){

        int u=Q[front++];

        for(int i=head[u];i!=-1;i=edge[i].next){

            int v=edge[i].to;

            if(edge[i].cap>edge[i].flow&&dep[v]==-1){

                dep[v]=dep[u]+1;

                if(v==t)

                    return true;

                Q[tail++]=v;

            }

        }

    }

    return false;

}

int dinic(int s,int t,int n=-1){

    int maxflow=0;

    if(n==-1)

        n=t;

    n++;//假如把t作为编号最后的点的话传入t就可以了

    while(bfs(s,t,n)){

        for(int i=0;i<n;i++)cur[i]=head[i];

        int u=s,tail=0;

        while(cur[s]!=-1){

            if(u==t){

                int tp=INF;

                for(int i=tail-1;i>=0;i--){

                    tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow);

                }

                maxflow+=tp;

                for(int i=tail-1;i>=0;i--){

                    edge[sta[i]].flow+=tp;

                    edge[sta[i]^1].flow-=tp;

                    if(edge[sta[i]].cap-edge[sta[i]].flow==0)

                        tail=i;

                }

                u=edge[sta[tail]^1].to;

            }

            else if(cur[u]!=-1&&edge[cur[u]].cap>edge[cur[u]].flow

                    &&dep[u]+1==dep[edge[cur[u]].to]){

                sta[tail++]=cur[u];

                u=edge[cur[u]].to;

            }

            else{

                while(u!=s&&cur[u]==-1){

                    u=edge[sta[--tail]^1].to;

                }

                cur[u]=edge[cur[u]].next;

            }

        }

    }

    return maxflow;

}

/* 备注：

1.检查MAXN与MAXM，注意预留反向边和额外边的位置

2.每次建图的第一次addedge()前必须先init()

3.不传入第三参数的dinic(s,t)需保证t是最后的结点

 */

/* dinic end */

int g[205][205];

int n,m,k;

inline int id(int i,int j){

    return (i-1)*m+j;

}

void add(int i,int j){

    if(i+1<=n&&j+3<=m&&g[i+1][j+3]==0){

        addedge(id(i,j),id(i+1,j+3));

    }

    if(i+3<=n&&j+1<=m&&g[i+3][j+1]==0){

        addedge(id(i,j),id(i+3,j+1));

    }

    if(i+3<=n&&j-1>=1&&g[i+3][j-1]==0){

        addedge(id(i,j),id(i+3,j-1));

    }

    if(i+1<=n&&j-3>=1&&g[i+1][j-3]==0){

        addedge(id(i,j),id(i+1,j-3));

    }

    if(i-1>=1&&j-3>=1&&g[i-1][j-3]==0){

        addedge(id(i,j),id(i-1,j-3));

    }

    if(i-3>=1&&j-1>=1&&g[i-3][j-1]==0){

        addedge(id(i,j),id(i-3,j-1));

    }

    if(i-3>=1&&j+1<=m&&g[i-3][j+1]==0){

        addedge(id(i,j),id(i-3,j+1));

    }

    if(i-1>=1&&j+3<=m&&g[i-1][j+3]==0){

        addedge(id(i,j),id(i-1,j+3));

    }

}

int main(){

    init();

    scanf("%d%d%d",&n,&m,&k);

    int s=0,t=n*m+1;

    for(int i=1;i<=k;i++){

        int x,y;

        scanf("%d%d",&x,&y);

        g[x][y]=1;

    }

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

        for(int j=1;j<=m;j++){

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

                continue;

            if((i+j)%2==0){

                //白格

                if(i%2==1){

                    //A类白格

                    addedge(s,id(i,j));

                    add(i,j);

                }

                else{

                    //规定从A类流到B类

                    addedge(id(i,j),t);

                }

            }

            else{

                //黑格

                if(i%2==1){

                    //A类黑格

                    addedge(s,id(i,j));

                    add(i,j);

                }

                else{

                    //规定从A类流到B类

                    addedge(id(i,j),t);

                }

            }

        }

    }

    int ans=n*m-k-dinic(s,t);

    printf("%d\n",ans);

}

巴特西

洛谷 - P5030 - 长脖子鹿放置 - 二分图最大独立集

最新文章

热门文章