CDQZ 0003:jubeeeeeat

2018-02-03 19:48:21来源:cnblogs.com作者:自为风月马前卒人点击

分享

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 31 0 11 1 11 0 11 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;}

相关文章

    无相关信息

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台