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=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;
}