CF818G Four Melodies 压缩图建边

看到题解有压缩图的tag，以为是很高大上的玩意

点进去发现竟然是不要建多余的边捏..

正确性：

如果a->下一个和它值差为1的元素，那么后面还有好几个和它值差为1的元素呢？

能完美代替，并且选择还更多。

思考一下流流动的过程，发现如果想满足跳着选的话这样建边也是可以实现的

给我的启发：建边上的优化

一些trick：只取四个序列，那么控制流量只为4，同理，该状态可以扩展到k序列

有个玄学..这道是加强版，过了以后它的弱化版CF813D Two Melodies没过，在某个地方数据出现了差1的答案

自己死活改不出来要来学长代码发现他打了个if mincost==-2139 hhh

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
using namespace std;
const int maxn=500010;
const int inf=INT_MAX;
bool vis[maxn];
int n,m,s,ss,t,x,y,z,f,dis[maxn],pre[maxn],last[maxn],flow[maxn],maxflow,mincost;
//dis最小花费;pre每个点的前驱；last每个点的所连的前一条边；flow源点到此处的流量 
struct Edge{
    int to,next,flow,dis;//flow流量 dis花费 
}edge[maxn];
int head[maxn],num_edge; 
queue <int> q;

void add_edge(int from,int to,int flow,int dis)
{
    edge[++num_edge].next=head[from];edge[num_edge].to=to;edge[num_edge].flow=flow;edge[num_edge].dis=dis;head[from]=num_edge;
    // 反向边流量为0，费用为负数
    edge[++num_edge].next=head[to];edge[num_edge].to=from;edge[num_edge].flow=0;edge[num_edge].dis=-dis;head[to]=num_edge;
}

bool spfa(int s,int t)
{
    memset(dis,0x7f,sizeof(dis));
    memset(flow,0x7f,sizeof(flow));
    memset(vis,0,sizeof(vis));
    q.push(s); vis[s]=1; dis[s]=0; pre[t]=-1;
    
    while (!q.empty())
    {
        int now=q.front();
        q.pop();
        vis[now]=0;
        for (int i=head[now]; i!=-1; i=edge[i].next)
        {
            if (edge[i].flow>0 && dis[edge[i].to]>dis[now]+edge[i].dis)//正边 
            {
                dis[edge[i].to]=dis[now]+edge[i].dis;
                pre[edge[i].to]=now;
                last[edge[i].to]=i;
                flow[edge[i].to]=min(flow[now],edge[i].flow);//
                if (!vis[edge[i].to])
                {
                    vis[edge[i].to]=1;
                    q.push(edge[i].to);
                }
            }
        }
    }
    return pre[t]!=-1;
}

void MCMF()
{ //int cnt=0;
    while (spfa(s,t))
    {//cnt++;
     //cout<<cnt<<endl;
        int now=t;
        maxflow+=flow[t];
        mincost+=flow[t]*dis[t];
        while (now!=s)
        {//从源点一直回溯到汇点 
            edge[last[now]].flow-=flow[t];//flow和dis容易搞混 
            edge[last[now]^1].flow+=flow[t];
            now=pre[now];
        }
    }
}
int a[maxn];
int main()
{
    //freopen("lys.in","r",stdin);
    memset(head,-1,sizeof(head)); num_edge=-1;//初始化 
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    // try 三拆点： in mid out 
    // in 1-n
    // mid :n+1,2*n
    // out: 2*n+1 -3*n
    s=0;
    t=3*n+1;
    for(int i=1;i<=n;i++){
        add_edge(s,i,1,0);// s->in 每个点要么选要么不选，流为1; 
        add_edge(i,i+n,1,-1);  // in->mid 强制选，费用-1 
        add_edge(i+n,2*n+i,inf,0); // mid->out 接强制选（似乎1也可以 
        add_edge(i,2*n+i,1,0); // in->out 不选 
        add_edge(2*n+i,t,1,0);
    }
    for(int i=1;i<=n;i++)
    {
      for(int j=i+1;j<=n;j++){
         if(a[i]==a[j]+1){
               add_edge(2*n+i,j,inf,0);// 因为不知道多少会经过所以是inf  
              break;
         }
      }    
      for(int j=i+1;j<=n;j++){
         if(a[i]==a[j]-1) {
               add_edge(2*n+i,j,inf,0);
               break;
         }
      }    
      for(int j=i+1;j<=n;j++){
         if(a[i]%7==a[j]%7){
               add_edge(2*n+i,j,inf,0);
               break;
         }
      }    
    }
    // t:3n+1 ss:3n+2 
    ss=3*n+2;
    add_edge(ss,s,4,0);
    s=ss;
    //cout<<"debug"<<endl;
    MCMF();
    cout<<-mincost;
    return 0;
}