CDQZ 0003:jubeeeeeat

2018-06-17 21:18:59来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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

 

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:洛谷P2891 [USACO07OPEN]吃饭Dining

下一篇:CSP201312-1:出现次数最多的数