CDQZ 0003:jubeeeeeat

总时间限制: 1000ms 内存限制: 256000kB描述

众所周知,LZF很喜欢打一个叫Jubeat的游戏。这是个音乐游戏,游戏界面是4×4的方阵,会根据音乐节奏要求玩家按下一些指定方块(以下称combo)。LZF觉得这太简单了,于是自己仿了个游戏叫Jubeeeeeat,唯一不同之处就是界面大小,Jubeeeeeat的界面为n×n的方阵。

在某一刻,界面同时出现了若干个combo。LZF终于觉得有些困难了,但毕竟LZF不是普通人,他有很多只手。LZF的手分为m只“肉质手”和q只“意念手”。顾名思义,“肉质手”是实际存在的手,每只肉质手都有5根手指,每根手指能按一个combo,但每只手的速度都不同,受限于此,LZF的每只肉质手的控制范围是一个固定大小的正方形。“意念手”即虚无之手,每只手只有1根手指,但控制范围为全局。

现在LZF想知道,他最多能按下多少个combo。

输入输入文件名为 jubeeeeeat.in。  第1行输入三个正整数n,m,q。 接下来是一个n×n的01矩阵,描述combo的位置,1为combo。 最后m行每行三个正整数xi,yi,ai,分别表示第i只肉质手掌控区域左上方块的行、列和边长。(行、列从1数起)输出输出文件名为 jubeeeeeat.out。  输出一个正整数,表示最多能按下的combo数。样例输入

3 1 3
1 0 1
1 1 1
1 0 1
1 1 2

样例输出

6

提示【数据说明】对于20%的数据,n=5,m=2,q=2;对于50%的数据,1≤n≤20,1≤m, q≤50;对于100%的数据,1≤n≤40,1≤m, q≤300,1≤xi, yi≤n,1≤xi+ai-1, yi+ai-1≤n。这道题比较容易看出是最大流构图的话,。。。。盗一下学长的图

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=8001,INF=5*1e8+10;
inline char nc()
{
    static char buf[MAXN],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    char c=nc();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
    return x*f;
}
int N,M,S=0,T=3001;
struct node
{
    int u,v,flow,nxt;
}edge[MAXN*20];
int head[MAXN],cur[MAXN],num=0;
inline void add_edge(int x,int y,int z)
{
    edge[num].u=x;
    edge[num].v=y;
    edge[num].flow=z;
    edge[num].nxt=head[x];
    head[x]=num++;
}
inline void AddEdge(int x,int y,int z) 
{
    add_edge(x,y,z);
    add_edge(y,x,0);
}int deep[MAXN];
inline bool BFS()
{
    memset(deep,0,sizeof(deep));
    deep[S]=1;
    queue<int>q;
    q.push(S);
    while(q.size()!=0)
    {
        int p=q.front();
        q.pop();
        for(int i=head[p];i!=-1;i=edge[i].nxt)
            if(!deep[edge[i].v]&&edge[i].flow)
            {
                deep[edge[i].v]=deep[p]+1;q.push(edge[i].v);
                if(edge[i].v==T) return 1;
            }
    }
    return deep[T];
}
int DFS(int now,int nowflow)
{
    if(now==T||nowflow<=0)    return nowflow;
    int totflow=0;
    for(int &i=cur[now];i!=-1;i=edge[i].nxt) 
    {
        if(deep[edge[i].v]==deep[now]+1&&edge[i].flow)
        {
            int canflow=DFS(edge[i].v,min(nowflow,edge[i].flow));
            edge[i].flow-=canflow;edge[i^1].flow+=canflow;
            totflow+=canflow;
            nowflow-=canflow;
            if(nowflow<=0) break;
        }
    }
    return totflow;
}
int Dinic()
{
    int ans=0;
    while(BFS())
    {
        memcpy(cur,head,sizeof(head)); 
        ans+=DFS(S,INF);
    }
    return ans;
}
int a[301][301],ID[301][301],tot=0;
struct Point
{
    int x,y,l;
}P[MAXN];
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    memset(head,-1,sizeof(head));
    int N=read(),M=read(),Num=read();
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            a[i][j]=read(),tot+=a[i][j],ID[i][j]=2*M+(i-1)*N+j;
    for(int i=1;i<=M;i++)
        P[i].x=read(),P[i].y=read(),P[i].l=read();
    for(int i=1;i<=M;i++)
    {
        AddEdge(S,i,INF),
        AddEdge(i,i+M,5);
    }
    for(int i=1;i<=M;i++)
        for(int j=1;j<=N;j++)
            for(int k=1;k<=N;k++)
                if( j >= P[i].x && j <= P[i].x+P[i].l-1 && k >= P[i].y && k<= P[i].y+P[i].l-1 && a[j][k])
                    AddEdge(i+M,ID[j][k],1);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            AddEdge(ID[i][j],T,1);
    int Maxflow=Dinic();
    Maxflow+=min(tot-Maxflow,Num);
    printf("%d",Maxflow);
    return  0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据小魔方

R语言可视化——用ggplot构造期待已久的雷达图

之前一直苦恼于ggplot函数无法制作雷达图,心想着既然饼图可以通过柱形图+极坐标模拟出来,为啥雷达图不行。 我尝试着用折线图+极坐标来模拟雷达图(之前在制作饼...

42260
来自专栏数据小魔方

地图可视化之——移花接木

本文所使用的代码是之前一篇关于航线图的数据,之所以要从新写一遍,是为了让大家体会借助在线地图制作地图可视化在代码效率上的便利(当然,也会有损失,你不能像操纵sh...

37960
来自专栏算法channel

Spark|有向无环图(DAG)检测

01 — Spark背景介绍 Apache Spark 是专为大规模数据处理而设计的快速通用的计算引擎。Spark 是一种与 Hadoop 相似的开源集群计算环...

62580
来自专栏儿童编程

Python案例——喝墨水的小乌龟

(本文为前一篇文章《理解编程语言只需四个词-编程知识体系介绍(带python及scratch案例)》的说明案例之一)

31720
来自专栏AI研习社

一次 PyTorch 的踩坑经历,以及如何避免梯度成为NaN

本文首发于知乎答主小磊在「PyTorch有哪些坑/bug?」下的回答,AI 研习社获原作者授权转载。 分享一下我最近的踩坑经历吧。 这几天在实现一个语义分割的 ...

1.9K60
来自专栏机器人网

滚珠丝杠你知多少,滚柱丝杠你又知多少?

滚珠丝杠的是将螺杆轴与螺母滚道内装进钢珠后进行无限的滚动和循环的一种机械形式,从而产生将旋转运动转化为精确直线定位运动。为减少钢珠在滚道内循环时产生的摩擦力矩,...

37690
来自专栏数据小魔方

动态地理信息可视化——leaflet在线地图简介

最近稍微涉猎了一下leaflet这个包,突然感到发现了动态可视化的新大门,这个包所提供的地图类型、动态效果、图层展示方式都大大扩展了ggplot作图系统的在数据...

59140
来自专栏数据魔术师

干货 | 变邻域搜索算法(VNS)求解TSP(附C++详细代码及注释)

上次变邻域搜索的推文发出来以后,看过的小伙伴纷纷叫好。小编大受鼓舞,连夜赶工,总算是完成了手头上的一份关于变邻域搜索算法解TSP问题的代码。今天,就在此...

1.6K20
来自专栏about云

使用Spark MLlib给豆瓣用户推荐电影

问题导读: 1.常用的推荐算法有哪些? 2.推荐系统是什么样的流程? 3.从这个推荐系统我们能学到什么? 推荐算法就是利用用户的一些行为,通过一些数学算法,推测...

90370
来自专栏CSDN技术头条

Google核心技术之——PageRank算法scala实现

PageRank算法简述 常言道,看一个人怎样,看他有什么朋友就知道了。也就是说,一个人有着越多牛X朋友的人,他是牛X的概率就越大。将这个知识迁移到网页上就是“...

31160

扫码关注云+社区

领取腾讯云代金券