【poj3020】 Antenna Placement

http://poj.org/problem?id=3020 (题目链接)

题意

　　给出一个矩阵，矩阵中只有‘＊’和‘o’两种字符，每个‘＊’可以向它上下左右四个方位上同为‘＊’的点连一条边，求最少需要连多少条边才能使所有‘＊’被至少一条边连接。

Solution

　　二分图最小路径覆盖。将每个‘＊’拆成两个节点构造一个二分图，然后连边，跑匈牙利就可以了。最小路径覆盖的答案就是所有节点的数量-最大匹配数/2。

代码

// poj3020

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define inf 2147483640

#define Pi 3.1415926535898

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=500;

struct edge {int to,next;}e[maxn<<2];

int a[maxn][maxn],head[maxn],vis[maxn],p[maxn],n,m,cnt;

char s[maxn];

void link(int u,int v) {

    e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;

}

bool find(int x) {

    for (int i=head[x];i;i=e[i].next) if (vis[e[i].to]!=cnt) {

           vis[e[i].to]=cnt;

           if (p[e[i].to]==0 || find(p[e[i].to])) {

               p[e[i].to]=x;

               return 1;

           }

        }

    return 0;

}

int main() {

    int T;scanf("%d",&T);

    while (T--) {

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

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

            scanf("%s",s);

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

                if (s[j]=='o') a[i+1][j+1]=0;

                else a[i+1][j+1]=1;

            }

        }

        int tot=0;cnt=0;

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

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

                if (a[i][j]>0) a[i][j]=++tot;

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

            for (int j=1;j<=m;j++) if (a[i][j]>0) {

                    if (a[i-1][j]>0) link(a[i][j],a[i-1][j]);

                    if (a[i+1][j]>0) link(a[i][j],a[i+1][j]);

                    if (a[i][j-1]>0) link(a[i][j],a[i][j-1]);

                    if (a[i][j+1]>0) link(a[i][j],a[i][j+1]);

                }

        int ans=0;cnt=0;

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

            cnt++;

            if (find(i)) ans++;

        }

        for (int i=1;i<=tot;i++) p[i]=head[i]=0;

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

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

            for (int j=1;j<=m;j++) a[i][j]=0;

    }

    return 0;

}