【NOI2018模拟3.26】Cti

2024-05-29 02:48
文章标签 模拟 3.26 cti noi2018

本文主要是介绍【NOI2018模拟3.26】Cti,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description

有一个 n × m 的地图, 地图上的每一个位置可以是空地, 炮塔或是敌人. 你需要操纵炮塔消灭敌人.
对于每个炮塔都有一个它可以瞄准的方向, 你需要在它的瞄准方向上确定一个它的攻击位置,当然也可以不进行攻击. 一旦一个位置被攻击, 则在这个位置上的所有敌人都会被消灭.
保证对于任意一个炮塔, 它所有可能的攻击位置上不存在另外一个炮塔.
定义炮弹的运行轨迹为炮弹的起点和终点覆盖的区域. 你需要求出一种方案, 使得没有两条炮弹轨迹相交.

Input

第一行两个整数 n,m.
接下来 n 行, 每行 m 个整数, 0 表示空地, −1,−2,−3,−4 分别表示瞄准上下左右的炮塔, 正整
数 p 表示表示此位置有 p 个敌人.

Output

一行一个整数表示答案.

Sample Input

输入1:
3 2
0 9
-4 3
0 -1

输入2:
4 5
0 0 -2 0 0
-4 0 5 4 0
0 -4 3 0 6
9 0 0 -1 0

Sample Output

输出1:
9

输出2:
12

Data Constraint

对于前 20% 的数据, n,m ≤ 5;
对于另 20% 的数据, 朝向上下的炮塔至多有 2 个;
对于另 20% 的数据, 至多有 6 个炮塔;
对于 100% 的数据, 1 ≤ n,m ≤ 50, 每个位置的敌人数量 < 1000.

Solution

一眼网络流。
然而这个的建模方法一前没弄过。
最小割模型。
对于横向射出的,依次连边连成一条链。
对于纵向的,依次反向连边练成一条链。
源点向横向的炮塔连正无穷,纵向炮塔向汇点连正无穷。
这样流都会从源点出发沿着边流到汇点。
而因为不能交叉,即不能存在这样的流,即割掉。
一开始把每个炮塔射程上的最大值统计进答案里,割表示选一个小一点的,即减掉一些,就是直接最小割就好了。
但是流从横的流到竖的后不能再流到横的那里。
所以分点就行了。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 100010
#define INF 214748347
using namespace std;
int S,T,n,m,last[N*10],nxt[N*10],to[N*10],data[N*10],tot=1,ans=0,d[N],bz[N],a[60][60];
void putin(int x,int y,int z)
{
    nxt[++tot]=last[x];last[x]=tot;to[tot]=y;data[tot]=z;
    nxt[++tot]=last[y];last[y]=tot;to[tot]=x;data[tot]=0;
}
bool bfs()
{
    int i=0,j=1;memset(bz,0,sizeof(bz));d[1]=S;bz[S]=1;
    while(i<j)
    {
        int x=d[++i];
        for(int k=last[x];k;k=nxt[k])
        if(bz[to[k]]==0&&data[k]>0) bz[to[k]]=bz[x]+1,d[++j]=to[k];
    }
    return bz[T]>0;
}
int dinic(int x,int v)
{
    if(x==T) return v;
    int ans=0;
    for(int i=last[x];i;i=nxt[i])
    {
        int y=to[i],qq=0;
        if(bz[y]==bz[x]+1&&data[i]>0)
        {
            qq=dinic(y,min(v,data[i]));
            if(qq) data[i]-=qq,ans+=qq,v-=qq,data[i^1]+=qq;
            if(v==0) return ans;
        }
    }
    if(ans==0) bz[x]=-1;
    return ans;
}
int p(int x,int y,int z)
{
    return (x-1)*m+y+n*m*z;
}
int main()
{
    freopen("cti.in","r",stdin);
    freopen("cti.out","w",stdout);
    scanf("%d%d",&n,&m);
    S=2*n*m+1;T=S+1;
    fo(i,1,n) fo(j,1,m) scanf("%d",&a[i][j]);
    fo(i,1,n)
    {
        fo(j,1,m)
        {
            putin(p(i,j,0),p(i,j,1),INF);
            if(a[i][j]==-1)
            {
                int jy=0;
                fd(k,i-1,1) jy=max(jy,a[k][j]);
                ans+=jy;
                a[i][j]=0;
                fd(k,i-1,1)
                {
                    putin(p(k,j,1),p(k+1,j,1),jy-a[k+1][j]);
                }
                putin(p(i,j,1),T,INF);
            }
            if(a[i][j]==-2)
            {
                int jy=0;
                fo(k,i+1,n) jy=max(jy,a[k][j]);
                ans+=jy;
                a[i][j]=0;
                fo(k,i+1,n)
                {
                    putin(p(k,j,1),p(k-1,j,1),jy-a[k-1][j]);
                }
                putin(p(i,j,1),T,INF);
            }
            if(a[i][j]==-3)
            {
                int jy=0;
                fd(k,j-1,1) jy=max(jy,a[i][k]);
                ans+=jy;
                a[i][j]=0;
                fd(k,j-1,1)
                {
                    putin(p(i,k+1,0),p(i,k,0),jy-a[i][k+1]);
                }
                putin(S,p(i,j,0),INF);
            }
            if(a[i][j]==-4)
            {
                int jy=0;
                fo(k,j+1,m) jy=max(jy,a[i][k]);
                ans+=jy;
                a[i][j]=0;
                fo(k,j+1,m)
                {
                    putin(p(i,k-1,0),p(i,k,0),jy-a[i][k-1]);
                }
                putin(S,p(i,j,0),INF);
            }
        }
    }
    while(bfs()) ans-=dinic(S,INF);
    printf("%d\n",ans);
}

这篇关于【NOI2018模拟3.26】Cti的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1012427

相关文章

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

hdu4431麻将模拟

给13张牌。问增加哪些牌可以胡牌。 胡牌有以下几种情况: 1、一个对子 + 4组 3个相同的牌或者顺子。 2、7个不同的对子。 3、13幺 贪心的思想: 对于某张牌>=3个,先减去3个相同,再组合顺子。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOExcepti

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

【算法专场】模拟(下)

目录 前言 38. 外观数列 算法分析 算法思路 算法代码 1419. 数青蛙 算法分析 算法思路 算法代码  2671. 频率跟踪器 算法分析 算法思路 算法代码 前言 在前面我们已经讲解了什么是模拟算法,这篇主要是讲解在leetcode上遇到的一些模拟题目~ 38. 外观数列 算法分析 这道题其实就是要将连续且相同的字符替换成字符重复的次数+

模拟实现vector中的常见接口

insert void insert(iterator pos, const T& x){if (_finish == _endofstorage){int n = pos - _start;size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;reserve(newcapacity);pos = _start + n;//防止迭代

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

1 模拟——67. 二进制求和

1 模拟 67. 二进制求和 给你两个二进制字符串 a 和 b ,以二进制字符串的形式返回它们的和。 示例 1:输入:a = "11", b = "1"输出:"100"示例 2:输入:a = "1010", b = "1011"输出:"10101" 算法设计 可以从低位到高位(从后向前)计算,用一个变量carry记录进位,如果有字符没处理完或者有进位,则循环处理。两个字符串对

AMAZING AUCTION(简单模拟)

AMAZING AUCTION 时间限制: 3000 ms  |  内存限制: 65535 KB 难度:4 描述 Recently the auction house hasintroduced a new type of auction, the lowest price auction. In this new system,people compete for the lo