首页 > 其他 > 详细

BZOJ1458 士兵占领

时间:2020-02-12 15:48:43      阅读:44      评论:0      收藏:0      [点我收藏+]

题意:

给定一个\(n\times m\)的方格,其中有一些障碍格子,限定每行每列分别至少要有的士兵数,问最少要摆多少个士兵。

知识点:

最大流

解法:

考虑在非障碍格子都摆上一个士兵,假如还是不够数,那么无解;
否则考虑哪些士兵可以去掉仍然满足限制条件。

所以源点连“该行可以摆放的数量-限定最小值”的边权到行的每个节点,同理,列的每个点连到汇点。

中间的连边是非障碍格子\(x\)连到\(y\),所以求出的最大流就是可以删掉的最多士兵。

用总共非障碍数-最大流即为答案。

备注:

个人认为这个做法比论文里讲的计算出最多贡献为2的个数那种方法更好理解一些。

代码:

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

const int maxn=110,maxm=20400,inf=0x7fffffff;
int n,m,K,S,T,a[maxn],b[maxn],tot,head[maxn<<1],dis[maxn<<1],cur[maxn<<1];
bool mp[maxn][maxn];
struct node
{
    int nxt,to,w;
}edge[maxm];
queue<int>q;

int read()
{
    int x=0;
    char c=getchar();
    while (c<48||c>57)
        c=getchar();
    while (c>=48&&c<=57)
        x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x;
}

void add(int u,int v,int w)
{
    edge[++tot]=(node){head[u],v,w};
    head[u]=tot;
}

#define link(u,v,w) (add((u),(v),(w)),add((v),(u),(0)))

int dfs(int u,int flow)
{
    if (u==T)
        return flow;
    int i,res=flow,v,tmp;
    for (i=head[u];i;i=edge[i].nxt)
    {
        v=edge[i].to;
        if (dis[v]==dis[u]+1&&edge[i].w>0)
        {
            tmp=dfs(v,min(edge[i].w,res));
            edge[i].w-=tmp;
            edge[i^1].w+=tmp;
            res-=tmp;
            if (!res)
                break;
        }
    }
    return flow-res;
}

bool bfs()
{
    while (!q.empty())
        q.pop();
    memset(dis,0,sizeof(dis));
    int i,u,v;
    q.push(S);
    dis[S]=1;
    while (!q.empty())
    {
        u=q.front();
        q.pop();
        for (i=head[u];i;i=edge[i].nxt)
        {
            v=edge[i].to;
            if (!dis[v]&&edge[i].w>0)
            {
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
    return dis[T];
}

int dinic()
{
    int ans=0,i,tmp;
    while (bfs())
    {
        for (i=1;i<=T;i++)
            cur[i]=head[i];
        tmp=dfs(S,inf);
        if (!tmp)
            break;
        ans+=tmp;
    }
    return ans;
}

int main()
{
    int i,j,k;
    tot=1;
    n=read(),m=read(),K=read();
    S=n+m+1,T=S+1;
    for (i=1;i<=n;i++)
        a[i]=m-read();
    for (i=1;i<=m;i++)
        b[i]=n-read();
    for (i=1;i<=K;i++)
    {
        j=read(),k=read();
        a[j]--,b[k]--;
        mp[j][k]=1;
    }
    for (i=1;i<=n;i++)
    {
        if (a[i]<0)
        {
            puts("JIONG!");
            return 0;
        }
        link(S,i,a[i]);
    }
    for (i=1;i<=m;i++)
    {
        if (b[i]<0)
        {
            puts("JIONG!");
            return 0;
        }
        link(i+n,T,b[i]);
    }
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            if (!mp[i][j])
                link(i,j+n,1);
    printf("%d\n",n*m-K-dinic());
    return 0;
}

BZOJ1458 士兵占领

原文:https://www.cnblogs.com/Ronald-MOK1426/p/12299297.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!