Qiuly

士兵占领 网络流 luoguP4311
讨厌死权限题了,然而这题又是 $bzoj$ 的权限题。$QwQ$ 只好去洛谷上做了,幸好洛谷收的题目比较多。这题就...
扫描右侧二维码阅读全文
24
2019/05

士兵占领 网络流 luoguP4311

讨厌死权限题了,然而这题又是 $bzoj$ 的权限题。

$QwQ$ 只好去洛谷上做了,幸好洛谷收的题目比较多。

这题就是网络流,我们先假设棋盘上摆满了士兵,这个时候需要拿走一些士兵,使得棋盘仍然是合法的,求拿走的最多数。

额……最多数让我想起了最大流,不过现在还是先来考虑怎么建图。

我们建两排点,第一排表示行,一共 $M$ 个点,第二排表示列,一共 $N$ 个点。对于一个点 $(x,y)$ ,就像从第一排的第 $x$ 号点向第二排的第 $y$ 号点连一条边权为 $1$ 的边。

这个显然是没有问题的。

然后就是限制,对于第 $k$ 行,至少要有 $L_k$ 个士兵,于是我们从 $s$ 连一条边权为 $L_k$ 的边,连向第一排的第 $k$ 号点。同样的道理,对于第二排的点,我们也像这样连边,连向

$t$ 。

然后就是跑 $dinic$ 了,别忘了跑出来的不是答案,而是最多拿走的士兵数,这个时候用整个棋盘的空位置的个数减去跑出来的 $maxflow$ 才是答案。

需要注意几个点:

  • 当我们在看到了一个行/列的时候,需要判断一下。假设这个是行,那么这行的位置显然有 $n$ 个,如果 $n$ 减去这行障碍的个数,再减去最少要放的士兵数后为负数,那么显然就怎么也不可能有合法的方案,于是直接输出 “JIONG” 就好了。
  • 注意整个棋盘的空位置不是 $N\cdot M$ ,而是 $N\cdot M-K$!
  • 数组大小的话只需要开到 $2n$ ,并不需要开到 $n^2$ ,因为只有两排点。但是边的数组大小需要开到 $n^2$ ,因为我们对于棋盘上的一个点就要连一条边表示它!

Code:

#include<cmath>
#include<queue>
#include<string>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>

#define A printf("A")
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))

const int N=2e2+5;
const int inf=1e9+9;

template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

std::queue<int> q;
struct Edge{int nxt,to,val;}G[N*N];
int n,m,k,s,t,cnt(1),dep[N],head[N];
int map[N][N],Li[N],Ci[N],Lm[N],Cm[N];

inline void add(int u,int v,int w){
    G[++cnt].nxt=head[u],G[cnt].to=v,G[cnt].val=w,head[u]=cnt;
    G[++cnt].nxt=head[v],G[cnt].to=u,G[cnt].val=0,head[v]=cnt; 
}

inline bool bfs(){
    memset(dep,0,sizeof(dep)); 
    q.push(s);dep[s]=1;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=G[i].nxt){
            int y=G[i].to;
            if(dep[y]||G[i].val<=0)continue;
            dep[y]=dep[x]+1,q.push(y);
        } 
    }return dep[t];
} 
inline int dfs(int x,int flow){
    if(x==t||!flow)return flow;
    int used=0,rlow;
    for(int i=head[x];i;i=G[i].nxt){
        int y=G[i].to;
        if(dep[y]==dep[x]+1&&G[i].val){
            used+=(rlow=dfs(y,min(G[i].val,flow-used)));
            G[i].val-=rlow,G[i^1].val+=rlow;
        }
    }if(!used)dep[x]=-1;
    return used;
}

inline int dinic(){
    int maxflow=0;
    while(bfs())maxflow+=dfs(s,inf);
    return maxflow;
}

int main(){
    IN(m),IN(n),IN(k);
    s=1,t=n+m+1;
    int atot=n*m-k;
    for(int i=1;i<=m;++i)IN(Li[i]);
    for(int i=1;i<=n;++i)IN(Ci[i]);
    for(int i=1;i<=k;++i){
        int x,y;IN(x),IN(y);
        map[x][y]=1,Lm[x]++,Cm[y]++;
    }
    for(int i=1;i<=m;++i)
        for(int j=1;j<=n;++j)
            if(!map[i][j])add(i,j+m,1);
    for(int i=1;i<=m;++i){
        int flow=n-Li[i]-Lm[i];
        if(flow<0){printf("JIONG!");exit(0);}
        else add(s,i,flow);
    }
    for(int i=1;i<=n;++i){
        int flow=m-Ci[i]-Cm[i];
        if(flow<0){printf("JIONG!");exit(0);}
        else add(i+m,t,flow);
    }
    printf("%d\n",atot-dinic());
    return 0;
}
最后修改:2019 年 05 月 30 日 03 : 24 PM

发表评论