中国建设工程招投标网站,微信小程序网站建设推广,集团建设网站,做网站要买什么服务器题目描述
小明最近在玩一款很好玩的游戏#xff0c;游戏规则是这样的#xff1a;
有一个n∗mn*mn∗m的地图#xff0c;地图上的每一个位置要么是空地#xff0c;要么是炮塔#xff0c;要么是一些敌人#xff0c;小明需要操纵炮塔攻击敌人。
攻击方法是#xff1a;对于…题目描述
小明最近在玩一款很好玩的游戏游戏规则是这样的
有一个n∗mn*mn∗m的地图地图上的每一个位置要么是空地要么是炮塔要么是一些敌人小明需要操纵炮塔攻击敌人。
攻击方法是对于每个炮塔游戏系统已经给出它可以瞄准的方向(上、下、左、右其中一个小明需要选择它的攻击位置每一个炮塔只能够攻击一个位置炮塔只能够向着它的瞄准方向上的某个位置发动攻击当然炮塔也可以不进行攻击。炮塔威力强大它可以且仅可以消灭目标位置上所有敌人。
出于安全考虑游戏系统已经保证不存在一个炮塔能够瞄准另外一个炮塔即对于任意一个炮塔它所有可能的攻击位置上不存在另外一个炮塔。而且如果把炮塔的起点和终点称为炮弹的运行轨迹那么系统不允许两条轨迹相交(包括起点和终点。
现在选定目标位置以后每一个炮塔同时开炮你要告诉小明他最多可以干掉多少敌人。
解析
这题的关键还是在建图上 先求出每个炮塔能打到的最大值加在一起设为tot 然后考虑冲突的情况 由于炮塔互相达不到因此冲突一定是横向与竖向的冲突 把每个点割成横点和竖点两个点横点向竖点连一条inf的边 然后对与每个横向炮塔连一条s到炮塔的inf的边 然后从这个炮塔一直往炮弹方向相邻地连边边权为 炮塔达到的最大值 - 边的起点格子的权值 竖向炮塔同理连向t点边的方向全反过来balabala… 这样不合法的情况就会使s与t联通 考虑割掉一条(i,j)(i,j)(i,j)到(i,j1)(i,j1)(i,j1)的边含义就是对应的炮塔改为攻击(i,j)(i,j)(i,j)的敌人并损失相应的代价 最后的答案就是 tot-最小割
代码
#includebits/stdc.h
#define ll long long
using namespace std;
const int N5050;
const int M1e9;
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();};while(isdigit(c)){xx*10c-0;cgetchar();}return x*f;
}
int n,m,s,t;
struct node{int to,nxt;ll cap;
}p[3000500];
int fi[N],cnt;
void addline(int x,int y,ll cap){p[cnt](node){y,fi[x],cap};fi[x]cnt;p[cnt](node){x,fi[y],0};fi[y]cnt;
}
int col[N],cur[N];
queueintq;
int bfs(){memset(col,0,sizeof(col));col[s]1;q.push(s);while(!q.empty()){int nowq.front();q.pop();for(int icur[now]fi[now];~i;ip[i].nxt){int top[i].to;if(col[to]||!p[i].cap) continue;col[to]col[now]1;q.push(to);}}return col[t];
}
ll dfs(int x,ll lim){if(xt||!lim) return lim;ll res0;for(int icur[x];~i;ip[i].nxt){int top[i].to;if(!p[i].cap||col[to]!col[x]1) continue;ll adddfs(to,min(lim,p[i].cap));lim-add;resadd;p[i].cap-add;p[i^1].capadd;if(!lim) break;}if(lim) col[x]-1;return res;
}
ll dinic(){ll res0;while(bfs()){while(ll tmpdfs(s,2e15)) restmp;}return res;
}
int vis[N];
void find1(int x){if(vis[x]) return;vis[x]1;for(int ifi[x];~i;ip[i].nxt){if(!p[i].cap) continue;find1(p[i].to);}return;
}
void find2(int x){if(vis[x]) return;vis[x]2;for(int ifi[x];~i;ip[i].nxt){if(!p[i^1].cap) continue;find2(p[i].to);}return;
}
#define id(x,y) ((x-1)*my)
int num,x,tot;
int dx[5]{0,-1,1,0,0},dy[5]{0,0,0,-1,1};
inline bool exi(int x,int y){return x1xny1ym;
}
int a[55][55],mx[2505];
struct tower{int x,y,op;int mx,xx,yy;
}o[2505];
#define heng(x,y) ((x-1)*my)
#define shu(x,y) ((x-1)*myn*m)
int main(){memset(fi,-1,sizeof(fi));cnt-1;nread();mread();for(int i1;in;i){for(int j1;jm;j){xread();if(x0) a[i][j]x;else{x-x;o[num](tower){i,j,x,0,i,j};}}}//printf(ok);for(int i1;inum;i){int xo[i].x,yo[i].y,opo[i].op;while(x1xny1ym){xdx[op];ydy[op];if(a[x][y]o[i].mx){o[i].mxa[x][y];o[i].xxx;o[i].yyy;}}toto[i].mx;}for(int i1;in;i){for(int j1;jm;j) addline(heng(i,j),shu(i,j),2e15);}s2*n*m1;ts1;for(int i1;inum;i){int xo[i].x,yo[i].y,opo[i].op;int xxo[i].xx,yyo[i].yy,mxo[i].mx;//a[x][y]2e9;if(op2){addline(shu(x,y),t,2e15);while(xx!x||yy!y){// printf((%d %d)-(%d %d) len%d\n,xx,yy,xx-dx[op],yy-dy[op],a[xx-dx[op]][yy-dy[op]]);addline(shu(xx,yy),shu(xx-dx[op],yy-dy[op]),mx-a[xx-dx[op]][yy-dy[op]]);xx-dx[op];yy-dy[op];}}else{addline(s,heng(x,y),2e15);while(x!xx||y!yy){// printf((%d %d)-(%d %d) len%d\n,x,y,xdx[op],ydy[op],a[x][y]);addline(heng(x,y),heng(xdx[op],ydy[op]),mx-a[x][y]);xdx[op];ydy[op];}}}printf(%d\n,tot-dinic());return 0;
}
/*
3 2 1 3
1 2 10
2 3 10
*/
