Cogs 1632. 搬运工(二分图最小点覆盖)

搬运工

★ 输入文件：worker.in 输出文件：worker.out 简单对比

时间限制：1 s 内存限制：256 MB

【题目描述】

小涵向小宇推荐了一款小游戏。

游戏是这样的，在一个n*n的地图中，有若干个格子上有障碍物。你需要雇佣搬运工，将这些障碍物全部清除。不过每次操作你只能让搬运工将某一行或者某一列的障碍物全部清除。如果你让搬运工清除第i行障碍物，需要付出ai元；如果你让搬运工清除第j列障碍物，需要付出bj元。

小涵告诉小宇，必须用尽可能少的次数消除这些障碍物。若有多种方案，则必须花费尽量少的费用。结果小宇想了很久仍然没有闯过第一关，只好向你求助了。

【输入格式】

第1行，一个正整数n。

第2~n+1行，每行n个字符。第i+1行的第j个字符表示地图的坐标(i, j)的格子（左上角为起点(1, 1)）。’*’表示障碍，’.’表示空格。

第n+2行，n个正整数，第i个数表示清除地图第i行的费用。

第n+3行，n个正整数，第i个数表示清除地图第i列的费用。

【输出格式】

输出2行。第1行是最少次数，第2行是在最少次数的前提下费用的最小值。

【样例输入】

3

…

.*.

**.

10 5 17

1 8 4

【样例输出】

2

9

【提示】

30%的数据满足对于任意i和j(1 <= i, j <= n)，有ai = bj。

100%的数据满足1 <= n <= 200，0 <= ai, bj <= 100.

[样例说明]一共有三个障碍物，坐标分别是(2, 2), (3, 1), (3, 2)。消除第1列和第2列是最优方案。

【来源】

HZOI

/*

网络流渣渣表示题解很神.

二分图的两边分别是行和列.

二分图的两边连障碍.

两侧有一侧消去这个障碍就消去了.

so 就转换成了最小点覆盖.

最小点覆盖:选取最少的点数,使这些点和所有的边都有关联(把所有的边的覆盖).

最小点覆盖数=最大匹配数=最大流.

这题还要求一个最小点覆盖下的最小花费.

我们把S到行的流量由1改为inf+a[i].

把列到T的流量由1改为inf+b[i].

于是我们就在不影响答案的情况下

同时算出了最大匹配和最小花费.

ansc=ans/inf,ansf=ans%inf;

*/

#include<iostream>

#include<cstdio>

#include<queue>

#define MAXN 410

#define INF 1e9

const int inf=1e6;

using namespace std;

int n,m,S,T,ans,cut=1,dis[MAXN],a[MAXN],b[MAXN],head[MAXN],ansf,ansc;

char g[MAXN][MAXN];

queue<int>q;

struct data{int u,v,next,c;}e[MAXN*MAXN*6];

int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

void add(int u,int v,int c)

{

    e[++cut].u=u;e[cut].v=v;e[cut].c=c;e[cut].next=head[u];head[u]=cut;

    e[++cut].u=v;e[cut].v=u;e[cut].c=0;e[cut].next=head[v];head[v]=cut;

}

bool bfs()

{

    for(int i=S;i<=T;i++) dis[i]=-1;dis[S]=0;

    q.push(S);

    while(!q.empty())

    {

        int u=q.front();q.pop();b[u]=0;

        for(int i=head[u];i;i=e[i].next)

        {

            int v=e[i].v;

            if(dis[v]==-1&&e[i].c)

            {

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

                q.push(v);

            }

        }

    }

    return dis[T]!=-1;

}

int dfs(int u,int y)

{

    if(u==T) return y;

    int rest=0;

    for(int i=head[u];i&&rest<y;i=e[i].next)

    {

        int v=e[i].v;

        if(dis[v]==dis[u]+1&&e[i].c)

        {

            int x=dfs(v,min(y-rest,e[i].c));

            e[i].c-=x;

            e[i^1].c+=x;

            rest+=x;

        }

    }

    if(!rest) dis[u]=-1;

    return rest;

}

void dinic()

{

    while(bfs()) ans+=dfs(S,INF);

    ansc=ans/inf,ansf=ans%inf;

}

int main()

{

    freopen("worker.in","r",stdin);

    freopen("worker.out","w",stdout);

    int x;

    n=read();S=0,T=2*n+1;

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

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

        cin>>g[i][j];

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

    {

        a[i]=read();

        add(S,i,inf+a[i]);

    }

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

    {

        b[i]=read();

        add(i+n,T,inf+b[i]);

    }

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

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

      {

        if(g[i][j]=='*') add(i,j+n,INF);

      }

    dinic();

    printf("%d\n%d",ansc,ansf);

    return 0;

}

巴特西

Cogs 1632. 搬运工(二分图最小点覆盖)

最新文章

热门文章