poj 3020 Antenna Placement（二分图最大匹配）

题意：

N行M列的矩阵，每个格子里不是 * 就是 O 。

* ：是一个利益点。

O：是一个空白点。

每次可以用一个圈覆盖相邻的两个*。（左右相邻或上下相邻）。

问最少需要多少个圈可以覆盖所有的*。

思路：

把每个格子变成一个数，总共有N*M个数。构造二分图，左右的数字都分别是1....N*M。

若两个*可以被一个圈覆盖，则将它们对应在左边、右边的点连上线。

答案即为：*的总数 - 最大二分匹配的值/2（因为有一半是对称的）。

代码：

int T,n,m;

vector<int> graph[405];

bool bmask[405];

int cx[405],cy[405];

char s[45][15];

int findPath(int u){

    int L=graph[u].size();

    rep(i,0,L-1){

        int v=graph[u][i];

        if(!bmask[v]){

            bmask[v]=true;

            if(cy[v]==-1||findPath(cy[v])){

                cy[v]=u;

                cx[u]=v;

                return 1;

            }

        }

    }

    return 0;

}

int MaxMatch(){

    int ans=0;

    rep(i,1,n*m) cx[i]=cy[i]=-1;

    rep(i,1,n*m) if(cx[i]==-1){

        mem(bmask,false);

        ans+=findPath(i);

    }

    return ans;

}

int main(){

    cin>>T;

    while(T--){

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

        rep(i,1,n*m) graph[i].clear();

        int cc=0;

        rep(i,1,n) scanf("%s",s[i]);

        rep(i,1,n){

            rep(j,0,m-1) if(s[i][j]=='*'){

                int num=m*(i-1)+j+1;

                int u=i, v=j+1;

                if(v-1>=1 && s[u][j-1]=='*') graph[num].push_back(num-1);

                if(v+1<=m && s[u][j+1]=='*') graph[num].push_back(num+1);

                if(u-1>=1 && s[u-1][j]=='*') graph[num].push_back(num-m);

                if(u+1<=n && s[u+1][j]=='*') graph[num].push_back(num+m);

                ++cc;

            }

        }

        int dd=MaxMatch();

        printf("%d\n",cc-dd/2);

    }

}

巴特西

poj 3020 Antenna Placement（二分图最大匹配）

最新文章

热门文章