益阳做网站的公司,莱芜论坛莱芜话题吕金梦,wordpress 如何分页,嘉兴学网站建设题目描述 Plants vs. Zombies#xff08;PVZ#xff09;是最近十分风靡的一款小游戏。Plants#xff08;植物#xff09;和Zombies#xff08;僵尸#xff09;是游戏的主角#xff0c;其中Plants防守#xff0c;而Zombies进攻。该款游戏包含多种不同的挑战系列#xf…题目描述 Plants vs. ZombiesPVZ是最近十分风靡的一款小游戏。Plants植物和Zombies僵尸是游戏的主角其中Plants防守而Zombies进攻。该款游戏包含多种不同的挑战系列比如Protect Your Brain、Bowling等等。其中最为经典的莫过于玩家通过控制Plants来防守Zombies的进攻或者相反地由玩家通过控制Zombies对Plants发起进攻。 现在我们将要考虑的问题是游戏中Zombies对Plants的进攻请注意本题中规则与实际游戏有所不同。游戏中有两种角色Plants和Zombies每个Plant有一个攻击位置集合它可以对这些位置进行保护而Zombie进攻植物的方式是走到植物所在的位置上并将其吃掉。 游戏的地图可以抽象为一个N行M列的矩阵行从上到下用0到N–1编号列从左到右用0到M–1编号在地图的每个位置上都放有一个Plant为简单起见我们把位于第r行第c列的植物记为Pr, c。 Plants分很多种有攻击类、防守类和经济类等等。为了简单的描述每个Plant定义Score和Attack如下 Score[Pr, c] Zombie击溃植物Pr, c可获得的能源。若Score[Pr, c]为非负整数则表示击溃植物Pr, c可获得能源Score[Pr, c]若为负数表示击溃Pr, c需要付出能源 -Score[Pr, c]。 Attack[Pr, c] 植物Pr, c能够对Zombie进行攻击的位置集合。 Zombies必须从地图的右侧进入且只能沿着水平方向进行移动。Zombies攻击植物的唯一方式就是走到该植物所在的位置并将植物吃掉。因此Zombies的进攻总是从地图的右侧开始。也就是说对于第r行的进攻Zombies必须首先攻击Pr, M-1若需要对Pr, c0≤cM-1攻击必须将Pr,M-1, Pr, M-2 … Pr, c1先击溃并移动到位置(r, c)才可进行攻击。 在本题的设定中Plants的攻击力是无穷大的一旦Zombie进入某个Plant的攻击位置该Zombie会被瞬间消灭而该Zombie没有时间进行任何攻击操作。因此即便Zombie进入了一个Plant所在的位置但该位置属于其他植物的攻击位置集合则Zombie会被瞬间消灭而所在位置的植物则安然无恙在我们的设定中Plant的攻击位置不包含自身所在位置否则你就不可能击溃它了。 Zombies的目标是对Plants的阵地发起进攻并获得最大的能源收入。每一次你可以选择一个可进攻的植物进行攻击。本题的目标为制定一套Zombies的进攻方案选择进攻哪些植物以及进攻的顺序从而获得最大的能源收入。 输入输出格式 输入格式 输入文件pvz.in的第一行包含两个整数N, M分别表示地图的行数和列数。 接下来N×M行描述每个位置上植物的信息。第r×M c 1行按照如下格式给出植物Pr, c的信息第一个整数为Score[Pr, c], 第二个整数为集合Attack[Pr, c]中的位置个数w接下来w个位置信息r’, c’表示Pr, c可以攻击位置第r’ 行第c’ 列。 输出格式 输出文件pvz.out仅包含一个整数表示可以获得的最大能源收入。注意你也可以选择不进行任何攻击这样能源收入为0。 说明 约20%的数据满足1 ≤ N, M ≤ 5 约40%的数据满足1 ≤ N, M ≤ 10 约100%的数据满足1 ≤ N ≤ 201 ≤ M ≤ 30-10000 ≤ Score ≤ 10000 能源收入有正有负再看数据范围20*30很容易想到是最大权闭合子图。 关键就是建模首先要从源点连向正能源的点从负能源边权要转正的点连向汇点。第二步从被保护的点连向保护的点(至于原因下面会解释)。最后因为僵尸只能从右往左走所以对于一行左面的点相当于被右面的点保护所以要从左面的点连向右面的点。因为有些点之间互相保护所以这些点一定不能到达就是有环被这些点保护的点也就不能到达所以我们要从网络中把这些点去掉判环最简单的方法自然是拓扑排序了把排序到的点标记上表示可以增广。将图中所有反向边进行拓扑排序如果之前连的是从保护点到被保护点的话删掉的就是环和保护环的点而不是被环保护的点。 拓扑排序之后直接跑最大流也就是最小割把正能源和正点权减掉最小割就得出答案了但要注意正能源和不要把删掉的点也计算进去我之前就是因为这里一直WA。 最后附上代码。 #includecstdio
#includealgorithm
#includeiostream
#includecstring
#includecmath
#includequeue
using namespace std;
queueintQ;
int next[1000001];
int to[1000001];
int val[1000001];
int head[1000001];
int tot1;
int q[1000001];
int vis[1000];
int n,m;
int S,T;
int ans;
int s[1000];
int x,y;
int sum;
int num;
int d[1000001];
int inv[10000];
const int INF0x3f3f3f3f;
void add(int x,int y,int v)
{tot;next[tot]head[x];head[x]tot;to[tot]y;val[tot]v;tot;next[tot]head[y];head[y]tot;to[tot]x;val[tot]0;inv[x];
}
bool bfs(int S,int T)
{int r0;int l0;memset(d,-1,sizeof(d));q[r]S;d[S]0;while(lr){int nowq[l];for(int ihead[now];i;inext[i]){if(d[to[i]]-1val[i]!0vis[to[i]]1){d[to[i]]d[now]1;q[r]to[i];}}l;}if(d[T]-1){return false;}else{return true;}
}
int dfs(int x,int flow)
{if(xT){return flow;}int now_flow;int used0;for(int ihead[x];i;inext[i]){if(d[to[i]]d[x]1val[i]!0vis[to[i]]1){now_flowdfs(to[i],min(flow-used,val[i]));val[i]-now_flow;val[i^1]now_flow;usednow_flow;if(now_flowflow){return flow;}}}if(used0){d[x]-1;}return used;
}
void dinic()
{while(bfs(S,T)true){ansdfs(S,INF);}
}
int main()
{scanf(%d%d,n,m);Sn*m1;Tn*m2;for(int i1;in*m;i){scanf(%d,s[i]);if(s[i]0){add(S,i,s[i]);}else if(s[i]0){add(i,T,-s[i]);}scanf(%d,num);while(num--){scanf(%d%d,x,y);add(x*my1,i,INF);}if(i%m){add(i,i1,INF);}}for(int i1;in*m2;i){if(inv[i]0){Q.push(i);}}while(!Q.empty()){int nowQ.front();vis[now]1;if(s[now]0){sums[now];}Q.pop();for(int ihead[now];i;inext[i]){if(i%21){inv[to[i]]--;if(inv[to[i]]0){Q.push(to[i]);}}}}dinic();sum-ans;printf(%d,sum);return 0;
} 转载于:https://www.cnblogs.com/Khada-Jhin/p/9113200.html
