CDQZ 0003:jubeeeeeat

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数。

样例输入

样例输出

提示

【数据说明】

对于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=,INF=*1e8+;

inline char nc()

{

    static char buf[MAXN],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,,MAXN,stdin),p1==p2)?EOF:*p1++;

}

inline int read()

{

    char c=nc();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=nc();}

    while(c>=''&&c<=''){x=x*+c-'';c=nc();}

    return x*f;

}

int N,M,S=,T=;

struct node

{

    int u,v,flow,nxt;

}edge[MAXN*];

int head[MAXN],cur[MAXN],num=;

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,);

}int deep[MAXN];

inline bool BFS()

{

    memset(deep,,sizeof(deep));

    deep[S]=;

    queue<int>q;

    q.push(S);

    while(q.size()!=)

    {

        int p=q.front();

        q.pop();

        for(int i=head[p];i!=-;i=edge[i].nxt)

            if(!deep[edge[i].v]&&edge[i].flow)

            {

                deep[edge[i].v]=deep[p]+;q.push(edge[i].v);

                if(edge[i].v==T) return ;

            }

    }

    return deep[T];

}

int DFS(int now,int nowflow)

{

    if(now==T||nowflow<=)    return nowflow;

    int totflow=;

    for(int &i=cur[now];i!=-;i=edge[i].nxt)

    {

        if(deep[edge[i].v]==deep[now]+&&edge[i].flow)

        {

            int canflow=DFS(edge[i].v,min(nowflow,edge[i].flow));

            edge[i].flow-=canflow;edge[i^].flow+=canflow;

            totflow+=canflow;

            nowflow-=canflow;

            if(nowflow<=) break;

        }

    }

    return totflow;

}

int Dinic()

{

    int ans=;

    while(BFS())

    {

        memcpy(cur,head,sizeof(head));

        ans+=DFS(S,INF);

    }

    return ans;

}

int a[][],ID[][],tot=;

struct Point

{

    int x,y,l;

}P[MAXN];

int main()

{

    #ifdef WIN32

    freopen("a.in","r",stdin);

    #else

    #endif

    memset(head,-,sizeof(head));

    int N=read(),M=read(),Num=read();

    for(int i=;i<=N;i++)

        for(int j=;j<=N;j++)

            a[i][j]=read(),tot+=a[i][j],ID[i][j]=*M+(i-)*N+j;

    for(int i=;i<=M;i++)

        P[i].x=read(),P[i].y=read(),P[i].l=read();

    for(int i=;i<=M;i++)

    {

        AddEdge(S,i,INF),

        AddEdge(i,i+M,);

    }

    for(int i=;i<=M;i++)

        for(int j=;j<=N;j++)

            for(int k=;k<=N;k++)

                if( j >= P[i].x && j <= P[i].x+P[i].l- && k >= P[i].y && k<= P[i].y+P[i].l- && a[j][k])

                    AddEdge(i+M,ID[j][k],);

    for(int i=;i<=N;i++)

        for(int j=;j<=N;j++)

            AddEdge(ID[i][j],T,);

    int Maxflow=Dinic();

    Maxflow+=min(tot-Maxflow,Num);

    printf("%d",Maxflow);

    return  ;

}