频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
jzoj5057 炮塔 网络流
2017-04-14 10:02:43         来源:Chunkit Lau’s blog  
收藏   我要投稿

jzoj5057 炮塔 网络流 :A君正在玩一款战略游戏,游戏中的规则是这样的:给定一个n*m的地图,地图上每一个位置要么是空地,要么是炮塔,要么有若干数量的敌人。现在A君要操控炮塔攻击这些敌人。

对于每个炮塔,它们的攻击方向已经确定(上下左右其中一个),A君只需要为每个炮塔指定攻击位置。每一个炮塔只能朝它攻击方向上的某个位置进行攻击,每个炮塔只能攻击一次,当然,炮塔也可以不进行攻击。炮塔对一个位置攻击后,位置上的所有敌人都会被消灭。

现在,游戏已经保证不存在一个炮塔能够攻击另一个炮塔的情况。但是,若把炮塔的位置与其攻击位置间的连线称为炮弹的运行轨迹,那么A君的攻击方案要保证不存在两条轨迹相交。现在每个炮塔选定攻击位置(或是不攻击)后,所有炮塔将会同时开炮进行攻击,请你告诉A君,他一次最多可以消灭多少敌人。

解题思路

考虑网络流,连边使得横向的炮台可以通过路径到的纵向的炮台,目标就是割掉一些边使得他们不连通,花费是点权的相反数,最小割即点权最大值,对边权加上最大值使其变正,减去最小割即可。

需要横纵分开建点,横连向纵,这样可以防止多次拐弯。

#include
#include
#include
#include
#include
#define LD double
#define LL long long
#define ULL unsigned long long
#define min(a,b) ((ab)?a:b)
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define fr(i,j) for(int i=begin[j];i;i=next[i])
using namespace std;
int const mn=5*1e3+9,mm=1e5+9,inf=1e9;
int n,m,ans,gra=1,a[60][60],begin[mn],vis[mn],dis[mn],size[mm],next[mm],to[mm],
    w[6][2]={{0,0},{-1,0},{1,0},{0,-1},{0,1}};
int num(int x,int y,int z){
    return ((x-1)*m+y)*2-z;
}
void insert2(int u,int v,int w){
    to[++gra]=v;
    size[gra]=w;
    next[gra]=begin[u];
    begin[u]=gra;
}
void insert(int u,int v,int w){
    insert2(u,v,w);
    insert2(v,u,0);
}
int updis(){
    int tmp=inf;
    fo(i,0,n*m*2+1)if(vis[i])fr(j,i)if(size[j]&&(!vis[to[j]]))
        tmp=min(tmp,dis[to[j]]+1-dis[i]);
    if(tmp==inf)return 0;
    fo(i,0,n*m*2+1)if(vis[i])dis[i]+=tmp;
    return 1;
}
int add(int now,int tar,int nsize){
    vis[now]=1;
    if(now==tar){
        ans-=nsize;
        return nsize;
    }
    fr(i,now)if((!vis[to[i]])&&size[i]&&(dis[now]==dis[to[i]]+1)){
        int tmp=add(to[i],tar,min(nsize,size[i]));
        if(tmp){
            size[i]-=tmp;size[i^1]+=tmp;
            return tmp;
        }
    }
    return 0;
}
int main(){
    //freopen("tower.in","r",stdin);
    //freopen("tower.out","w",stdout);
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    scanf("%d%d",&n,&m);
    fo(i,1,n)fo(j,1,m)scanf("%d",&a[i][j]),insert(num(i,j,0),num(i,j,1),inf);
    fo(i,1,n)fo(j,1,m)if(a[i][j]<0){
        int mx=0;
        fo(k,1,n){
            int ii=i+k*w[-a[i][j]][0],jj=j+k*w[-a[i][j]][1];
            if((1<=ii)&&(ii<=n)&&(1<=jj)&&(jj<=m))mx=max(mx,a[ii][jj]);
            else break;
        }
        ans+=mx;
        if((a[i][j]==-1)||(a[i][j]==-2)){
            insert(0,num(i,j,0),mx);
            fo(k,1,n){
                int ii=i+k*w[-a[i][j]][0],jj=j+k*w[-a[i][j]][1];
                if((1<=ii)&&(ii<=n)&&(1<=jj)&&(jj<=m))
                    insert(num(ii-w[-a[i][j]][0],jj-w[-a[i][j]][1],0),num(ii,jj,0),
                        min(mx,mx-a[ii-w[-a[i][j]][0]][jj-w[-a[i][j]][1]]));
                else break;
            }
        }else if((a[i][j]==-3)||(a[i][j]==-4)){
            insert(num(i,j,1),n*m*2+1,mx);
            fo(k,1,n){
                int ii=i+k*w[-a[i][j]][0],jj=j+k*w[-a[i][j]][1];
                if((1<=ii)&&(ii<=n)&&(1<=jj)&&(jj<=m))
                    insert(num(ii,jj,1),num(ii-w[-a[i][j]][0],jj-w[-a[i][j]][1],1),
                        min(mx,mx-a[ii-w[-a[i][j]][0]][jj-w[-a[i][j]][1]]));
                else break;
            }
        }
    }
    do{
        fo(i,0,n*m*2+1)vis[i]=0;
        while(add(0,n*m*2+1,inf))
            fo(i,0,n*m*2+1)vis[i]=0;
    }while(updis());
    printf("%d",ans);
    return 0;
}
点击复制链接 与好友分享!回本站首页
上一篇:多线程系列提高(3)--对象的共享
下一篇:KNN算法示例
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站