UVA 12549 Sentry Robots （最小点覆盖）

这道题挺像hdu 5093 Battle ships的，不过那道题是要求最多放置的点数，而这道题是要求最小点覆盖。

顶点覆盖的定义是：在G中任意边至少有一个端点属于顶点集合S。

一个重要的位置有(x,y)两个坐标，而要守住这个这个位置就是相当于连了一条边x到y的边。

选了一个(x,y)就相当于选了所有相同的x的边或者所有相同的y的边。

当所有的x或y被选完的时候就完成了看守。相当于是割断了x和y，所以就是最小割，对于容量为1的模型可以用匈牙利算法。

有了障碍以后只要把障碍两边的分开考虑就行了，拆一下点。

数组开大点不要RE啦

#include<bits/stdc++.h>

using namespace std;

const int N = ;

const int maxn = ;

char g[maxn][maxn];

int Yid[maxn][maxn],Y_cnt;

int match[N];

int dfsT[N],dfsTime;

vector<int> G[N];

#define PB push_back

bool dfs(int u)

{

    for(int i = ; i < G[u].size(); i++){

        int v = G[u][i];

        if(dfsT[v] != dfsTime){

            dfsT[v] = dfsTime;

            if(!~match[v] || dfs(match[v])){

                match[v] = u; return true;

            }

        }

    }

    return false;

}

int MaxMatch()

{

    int ret = ;

    memset(match,-,sizeof(match));

    memset(dfsT,,sizeof(dfsT));

    dfsTime = ;

    for(int i = ; i < Y_cnt; i++){

        dfsTime++;

        if(dfs(i)) ret++;

    }

    return ret;

}

int main()

{

   // freopen("in.txt","r",stdin);

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

    while(C--){

        int Y, X, P; scanf("%d%d%d",&Y,&X,&P);

        memset(g,,sizeof(g));

        while(P--) {

            int r,c;scanf("%d%d",&r,&c);

            g[r][c] = '*';

        }

        scanf("%d",&P);

        while(P--){

            int r,c;scanf("%d%d",&r,&c);

            g[r][c] = '#';

        }

        Y_cnt = ;

        for(int i = ; i <= Y;i++){

            bool flag = false;

            for(int j = ; j <= X; j++){

                if(g[i][j] == '*') flag = true,Yid[i][j] = Y_cnt;

                else if(g[i][j] == '#' && flag) Y_cnt++;

            }

            if(flag) Y_cnt++;

        }

        for(int i = ; i < Y_cnt; i++) G[i].clear();

        int X_cnt = ;

        for(int j = ; j <= X; j++){

            bool flag = false;

            for(int i = ; i <= Y; i++){

                if(g[i][j] == '*') {

                    flag = true;

                    G[Yid[i][j]].PB(X_cnt);

                }else if(g[i][j] == '#'&&flag){

                    X_cnt++;

                }

            }

            if(flag) X_cnt++;

        }

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

    }

    return ;

}

巴特西

UVA 12549 Sentry Robots （最小点覆盖）

最新文章

热门文章