【题解】调整圣剑

· · 题解

【题解】调整圣剑

首先，这是个最小割模型。

建分层图，一共 k 层，每层 n+1 个点 ， n 条边，第 i 条边的权值为 a_i ，割掉这条边表示这次选择了第 i 个护符。

考虑限制，对于限制 (i,j,x,y) 我们从第 i 层的第 x+1 个点向第 j 层的第 n-y+1 个点连一条权值为 INF 的边，这样如果第 i 层不割掉前 x 条边中的一条且第 j 层不割掉后 y 条边中的一条，就会出现一条路径，不符合最小割定义。

最后从源点向每一层的第一个点连 INF 边，从每一层的最后一个点向汇点连 INF 的边，就可以跑 MaxFlow-MinCut 了。

那么有了这两点思路后，我们可以把样例 1 的图建出来。

但是发现以 n \le 10^5 ， k,q \le 10^4 的数据量， n \times k 个点连建都建不出来。

怎么优化呢？从最大流的角度思考。我们发现原图里有很多长长的链。

这些链代表了 1-n 中的一些区间。对于这些只能向一个方向流的链，我们显然可以将这些链缩成边，边的容量为这些链流量中的最小值。由于是区间最小值，用 RMQ 即可。

到了这一步还没有结束。

有时候会出现这样的情况，导致一次选择选取了两个护符，因此我们需要把每一条边加上一个大数（如 10^{10}），使得割 k+1 条边的情况严格劣于割 k 条边的情况。

于是我们获得了最终的建图方式，以下是样例 3 的建图。

分析一下复杂度：一开始有 k 条边，每加一个限制会多出 2 个点和 3 条边，边和点的数量级都和 k,q 相同（即 10^4） ，跑 Dinic 可以通过，当然要是你觉得这个理论复杂度不符的话，可以换更快的网络流算法。

附上 std 


#include<bits/stdc++.h>
#define N 40010
#define M 500010
#define mk make_pair
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
namespace MaxFlow{
    int cnt=1,head[N],cur[N],dep[N],to[M],nxt[M];
    ll val[M],INF=1e14;
    void insert(int u,int v,ll w){
        cnt++;
        to[cnt]=v;
        val[cnt]=w;
        nxt[cnt]=head[u];
        head[u]=cnt;
    }
    void ins(int u,int v,ll w) {
        insert(u,v,w);
        insert(v,u,0);
    }
    bool bfs(int ss,int tt) {
        queue<int> q;
        memset(dep,0,sizeof(dep));
        q.push(ss),dep[ss]=1;
        while(!q.empty()) {
            int now=q.front();q.pop();
            for(int i=head[now]; i; i=nxt[i]) 
                if(val[i]&&!dep[to[i]]) {
                    dep[to[i]]=dep[now]+1;
                    q.push(to[i]);
                }
        }
        return dep[tt]!=0;
    }
    ll dfs(int now,ll dis,int tt) {
        if(now==tt) return dis;
        ll res=0;
        for(int& i=cur[now]; i; i=nxt[i])
            if(val[i]&&dep[to[i]]==dep[now]+1) {
                ll tmp=dfs(to[i],min(dis-res,val[i]),tt);
                res+=tmp,val[i]-=tmp,val[i^1]+=tmp;
                if(res==dis) return res;
            }
        if(!res) dep[now]=-1;
        return res;
    }
    ll Dinic(int ss,int tt) {
        ll res=0;
        while(bfs(ss,tt)) {
            memcpy(cur,head,sizeof(head));
            while(ll tmp=dfs(ss,INF,tt)) res+=tmp;
        }
        return res;     
    }
}
inline ll read() {
    ll res=0,f=1;char ch=getchar();
    while(!isdigit(ch)) f=ch=='-'?-1:1,ch=getchar();
    while(isdigit(ch)) res=res*10+ch-'0',ch=getchar();
    return f*res;
}
using namespace MaxFlow; 
vector<int> cut[M];//分割点 
int n,k,q,a[M],mn[M][22],lg[M];
int RMQ(int l,int r) { 
    int lg2=lg[r-l+1]; 
    return min(mn[l][lg2],mn[r-(1<<lg2)+1][lg2]);
}
int tot,s,t;
map<pii,int> mp;
pii b1[M],b2[M];
int main()
{
    n=read(),k=read(),q=read();s=0,t=40000;
    for(int i=2; i<=n; i++) lg[i]=lg[i/2]+1;
    for(int i=1; i<=n; i++) a[i]=mn[i][0]=read();
    for(int d=1; d<=q; d++) {
        int i=read(),j=read(),x=read(),y=read();
        if(x==n||y==n) continue;//特判，如果x或y为n表示其中一个选了任意一个都满足条件，相当于没有条件 
        cut[i].push_back(x),cut[j].push_back(n-y);
        b1[d]=mk(i,x),b2[d]=mk(j,n-y);
    }
    for(int i=1; i<=n; i++) sort(cut[i].begin(),cut[i].end());
    for(int d=1; d<20; d++)//RMQ
        for(int i=1; i+(1<<d)-1<=n; i++) mn[i][d]=min(mn[i][d-1],mn[i+(1<<(d-1))][d-1]);
    for(int i=1; i<=k; i++) {
        cut[i].push_back(n);//最后一段即使没有也得缩 
        int now=0,nid=++tot;
        ins(s,nid,INF);
        for(int j=0; j<cut[i].size(); j++) 
            if(!j||(j>0&&cut[i][j]!=cut[i][j-1]))//有可能有重复点 
                ins(nid,++tot,RMQ(now+1,cut[i][j])+1e10),//防止一条边选多次 
                now=cut[i][j],nid=tot,mp[mk(i,cut[i][j])]=tot;
        ins(nid,t,INF);
    } 
    for(int i=1; i<=q; i++) ins(mp[b1[i]],mp[b2[i]],INF);
    ll ans=Dinic(s,t)-k*1e10;
    printf("%lld",ans);
    return 0;
}