[bzoj 1458] 士兵占领(网络流dinic)

2018-02-03 19:47:31来源:cnblogs.com作者:GameTheory人点击

分享

1458: 士兵占领

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 784  Solved: 458
[Submit][Status][Discuss]

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  可以考虑拆点建网络流图由源点向所有可以放置士兵的位置连一条容量为2的边,再由每个位置向它所属的行和列的点连边容量为1,然后由所有的行和列向汇点连边,容量为该行(该列)所需的士兵个数。然后套dinic版子。。。。话说那玩意真的难写5555 

考虑 为什么源点向放置士兵的位置连边为2?

我是这么想的,因为一个位置不仅需要向他所在的列连边还需要向他所在的行连边,但是行和列是互不影响的,所以只能分别补充,因为补充的容量为1,所以每个点只能算一次。

 因为这样连边每个点被算了两次所以算出来之后ans要除以2  刚入cnblogs,第一篇题解...... 代码有点丑,将就看下23333
#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<queue>using namespace std;#define inf 2147483647void read(int &x) {    char ch; bool ok;    for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;    for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;}struct edge{    int w,v,nxt;}e[1000000];int head[30000],tot,level[30000],n,m,k;void ad(int u,int v,int w){    e[tot].v=v;    e[tot].w=w;    e[tot].nxt=head[u];    head[u]=tot++;}void add(int u,int v,int w){ad(u,v,w),ad(v,u,0);}int bfs(int s,int t){    memset(level,-1,sizeof(level));    queue<int> q;    q.push(s);level[s]=0;    while(!q.empty())    {        int u=q.front();q.pop();        for(int i=head[u];~i;i=e[i].nxt)            if(e[i].w>0&&level[e[i].v]<0)                level[e[i].v]=level[u]+1,q.push(e[i].v);    }    return level[t]>0;}int dfs(int u,int t,int f){    if(u==t) return f;    for(int i=head[u];~i;i=e[i].nxt)        if(level[e[i].v]>level[u]&&e[i].w>0)        {            int d=dfs(e[i].v,t,min(f,e[i].w));            if(d>0){e[i].w-=d,e[i^1].w+=d;return d;}        }    level[u]=-1;    return 0;}int solve(int s,int t){    int flow=0,f;    while(bfs(s,t)){while(f=dfs(s,t,inf)) flow+=f;}    return flow;}bool mp[104][104];int main(){    memset(mp,true,sizeof(mp));    read(m),read(n),read(k);    memset(head,-1,sizeof(head));    int x,y,z;    int s=0,t=n*m+m+n+1;int ans=0;    for(int i=1;i<=m;i++)read(x),add(i+n+n*m,t,x);    for(int i=1;i<=n;i++)read(x),add(i+n*m,t,x);    for(int i=1;i<=k;i++) read(x),read(y),mp[x][y]=false;    for(int i=1;i<=m;i++)        for(int j=1;j<=n;j++)            if(mp[i][j]) add(s,(i-1)*n+j,2),add((i-1)*n+j,i+n+n*m,1),add((i-1)*n+j,j+n*m,1);    printf("%d/n",solve(s,t)/2);}

相关文章

    无相关信息

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台