【刷题】BZOJ 1458 士兵占领

Description

有一个M * N的棋盘，有的格子是障碍。现在你要选择一些格子来放置一些士兵，一个格子里最多可以放置一个士兵，障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘当满足第i行至少放置了Li个士兵, 第j列至少放置了Cj个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。

Input

第一行两个数M, N, K分别表示棋盘的行数，列数以及障碍的个数。 第二行有M个数表示Li。 第三行有N个数表示Ci。 接下来有K行，每行两个数X, Y表示(X, Y)这个格子是障碍。

Output

输出一个数表示最少需要使用的士兵个数。如果无论放置多少个士兵都没有办法占领整个棋盘，输出”JIONG!” (不含引号)

Sample Input

4 4 4
1 1 1 1
0 1 0 3
1 4
2 2
3 3
4 3

Sample Output

4
数据范围
M, N <= 100, 0 <= K <= M * N

Solution

这题是自己想了个麻烦一点，慢了一点的算法，但是思路特简单
一行一列只能有一个，套路，行列连边
超级源点向所有行连边，流量为行上需要布满的士兵，费用为 \(0\)
所有列向超级汇点连边，流量为列上需要布满的士兵，费用为 \(0\)
如果某个位置没有障碍，那么将它的行列连边，流量为 \(1\) ，费用为 \(1\)
跑费用流
然后判断源点连出的和流向汇点的边是否满流，满了就是满足行列限制了，否则无解
有解的话输出费用

#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN=200+10,MAXM=MAXN*MAXN+10,inf=0x3f3f3f3f;
int n,m,k,e=1,clk,s,t,answas,beg[MAXN],cur[MAXN],level[MAXN],p[MAXN],vis[MAXN],G[MAXN][MAXN],to[MAXM<<1],nex[MAXM<<1],cap[MAXM<<1],was[MAXM<<1],out[MAXM<<1];
std::queue<int> q;
template<typename T> inline void read(T &x)
{
    T data=0,w=1;
    char ch=0;
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
    x=data*w;
}
template<typename T> inline void write(T x,char ch='\0')
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
    if(ch!='\0')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void insert(int x,int y,int z,int w)
{
    to[++e]=y;
    nex[e]=beg[x];
    out[e]=x;
    beg[x]=e;
    cap[e]=z;
    was[e]=w;
    to[++e]=x;
    nex[e]=beg[y];
    out[e]=y;
    beg[y]=e;
    cap[e]=0;
    was[e]=-w;
}
inline bool bfs()
{
    memset(level,inf,sizeof(level));
    level[s]=0;
    p[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        p[x]=0;
        for(register int i=beg[x];i;i=nex[i])
            if(cap[i]&&level[to[i]]>level[x]+was[i])
            {
                level[to[i]]=level[x]+was[i];
                if(!p[to[i]])p[to[i]]=1,q.push(to[i]);
            }
    }
    return level[t]!=inf;
}
inline int dfs(int x,int maxflow)
{
    if(x==t||!maxflow)return maxflow;
    vis[x]=clk;
    int res=0;
    for(register int &i=cur[x];i;i=nex[i])
        if((vis[x]^vis[to[i]])&&cap[i]&&level[to[i]]==level[x]+was[i])
        {
            int f=dfs(to[i],min(maxflow,cap[i]));
            res+=f;
            cap[i]-=f;
            cap[i^1]+=f;
            answas+=f*was[i];
            maxflow-=f;
            if(!maxflow)break;
        }
    return res;
}
inline void MCMF()
{
    while(bfs())clk++,memcpy(cur,beg,sizeof(cur)),dfs(s,inf);
}
int main()
{
    read(n);read(m);read(k);
    s=n+m+1,t=s+1;
    for(register int i=1,x;i<=n;++i)read(x),insert(s,i,x,0);
    for(register int i=1,x;i<=m;++i)read(x),insert(i+n,t,x,0);
    while(k--)
    {
        int x,y;read(x);read(y);
        G[x][y]=1;
    }
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j)
            if(!G[i][j])insert(i,j+n,1,1);
    MCMF();
    for(register int i=2;i<=e;i+=2)
        if((out[i]==s||to[i]==t)&&cap[i])
        {
            puts("JIONG");
            return 0;
        }
    write(answas,'\n');
    return 0;
}

【刷题】BZOJ 1458 士兵占领

原文：https://www.cnblogs.com/hongyj/p/9417345.html