首页 > 其他分享 >最小割解决广义差分约束问题

最小割解决广义差分约束问题

时间：2024-09-26 13:24:24浏览次数：8  
标签：tmp geq return int res 最小 差分 dep 广义

描述

该做法解决了一类“广义差分约束”问题（当然名字是我自己取的），除了可以解决常见的求解 \(A_1+c_1\geq A_2,A_2+c_2\geq A_3\dots\) 问题外，还可以求解形如“如果 \(A_1\geq c_1\)，那么 \(A_2\geq c_2\)”这样涉及条件逻辑运算的问题。另外，变量的取值还可以带权，即 \(A_i\) 取值 \(k\) 时的代价可以不为 \(k\) 而其他指定的数，求最小代价，当然如果代价取值就为 \(k\) 则会求出满足约束的和最小的一组解。

但这个做法也有很大的弊端，它的节点规模是约为变量数 \(\times\) 值域的，复杂度增长非常快，且它要求值域是离散的。

下文记值域为大写 \(C\)，而小写 \(c\) 意为常数，请勿混淆。

基本形式

我们将一个变量的取值从小到大连成一条链，一直连到最大取值 \(+1\) 所代表的节点，即 \(1\rightarrow 2\rightarrow 3\rightarrow\cdots\rightarrow (C_{max}-1)\rightarrow C_{max}\rightarrow (C_{max}+1)\) 这样的一条链。而对于一条 \(u\) 连到 \(u+1\) 的边，边权设为该变量取 \(u\) 值时的代价，注意这个代价可以不是随着高度而递增的；同时还需要建一条 \(u+1\) 到 \(u\) 的反边，边权为 \(INF\) （下文图片省略了反边）。

问题的基本形式是“如果 \(A_1\geq c_1\)，那么 \(A_2\geq c_2\)”，我们把代表 \(A_1\) 的链上表示 \(c_1\) 的节点向代表 \(A_2\) 链上的表示 \(c_2\) 的节点连一条边权为 \(INF\) 的边。

于是当我们再将所有链头与一个超级源点 \(S\)，所有链尾与一个超级汇点 \(T\) 连上边权为 \(INF\) 的边后，跑最小割，我们发现：

1

将 \(INF\) 边视为不能被割的边，我们发现，如果 \(A_1\) 的链割了 \((u,u+1),u\geq 4\) 的边，那么 \(A_2\) 就必须割 \(u\geq 2\) 的边，否则该网络仍会流通。假设将 \((u,u+1)\) 这条边被割视为这个变量取值为 \(u\)，这样就可以找到满足如果 \(A_1\geq 4\)，那么 \(A_2\geq 2\) 的最小代价取值方案！

链上割边唯一性定理

可以证明，一条变量所表示的链上只有可能有一个割，否则不优。

考虑最小割中，当一个割边是最优的时候，它一定是一侧能连通至 \(S\)，一侧能连通至 \(T\)，否则完全没必要在此处设割。

我们假设一条链上存在不止一个割时最优，我们关注距离 \(S\) 最近的与距离 \(T\) 最近的这两个割，前者的边起点能连通 \(S\)，终点能连通 \(T\)，后者反之。由于反向 \(INF\) 边的存在，这种情况下 \(S\) 就能到达 \(T\)，因此不可能存在多于一个割。

2

推广

  • \(A_2\geq A_1+c\)

    我们可以将 \(A_1\geq A_2+c\) 的条件完全等价转化为 \(\forall x\in C\)，如果 \(A_1\geq x\)，那么 \(A_2\geq x+c\)。因此我们对于 \(x\) 的每一种取值，都仿照基本形式建立一条横跨两个变量的链之间的边即可。

    如 \(A_2\geq A_1+2,C=\{1,2,3,4\}\) 的情况：

    注意到最后一条连的边是到 \(C_{max}+1\) 的，这么做是为了处理边界情况。

    3

  • \(A_1>c\)

    如果我们需要某个变量恒大于某个常数，可以从 \(S\) 连一条 \(INF\) 边到该变量链对应值处，这样保证了割无论如何都不会小于该值。

    如 \(A_1\geq 3\) 的情况：

    4

  • 如果 \(A_1\geq c_1\)，那么 \(A_2< c_2\)

    此时可以将 \(A_2\) 链上的值逆序，但链本身的指向不变，此时如果 \((u,u+1)\) 这条边被割表示该变量取值为 \(u+1\)。由于被翻转，因此这种做法是无法处理“如果 \(A_1\geq c_1\)，那么 \(A_2\geq c_2\)”和“如果 \(A_1\geq c_1\)，那么 \(A_2< c_2\)”同时存在的情况的。

    如 \(A_1\geq 4\) 那么 \(A_2< 3\) 的情况：

    5

例题

[HNOI2013] 切糕

题意

Link

题目给定一个 \(P\times Q\) 矩形的每个点取每个值的代价，让我们找出满足某个点的值和其上下左右点之差均小于等于 \(D\) 的情况下的最小代价。

转化

将“两点 \(A_1\) 与 \(A_2\) 之差小于等于 \(D\)”的条件转化为 \(A_1-D\leq A_2\leq A_1+D\)，再转化为 \(A_2\geq A_1-D\) 与 \(A_1\geq A_2-D\)，即是说对于任意相邻两点，它们之间的链是这样互相交叉连边的：

6

另外，本题不需要连上文所述的反向边以保证每条链只有一个割，因为边都是由大的值连向小的值且所有的点均有连边，一条链上多个割一定是不优的。[1]

代码 
#include<bits/stdc++.h>
#define getid(x,y,z) (((x)-1)*q*(r+1)+((y)-1)*(r+1)+(z))
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar __getchar
inline char __getchar(){
    static char ch[1<<20],*l,*r;
    return (l==r&&(r=(l=ch)+fread(ch,1,1<<20,stdin),l==r))?EOF:*l++;
}
#endif
template<class T>inline void rd(T &x){
    T res=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while('0'<=ch && ch<='9'){res=res*10+ch-'0';ch=getchar();}
    x=res*f;
}
template<class T>inline void wt(T x,char endch='\0'){
    static char wtbuff[20];
    static int wtptr;
    if(x==0){
        putchar('0');
    }
    else{
        if(x<0){x=-x;putchar('-');}
        wtptr=0;
        while(x){wtbuff[wtptr++]=x%10+'0';x/=10;}
        while(wtptr--) putchar(wtbuff[wtptr]);
    }
    if(endch!='\0') putchar(endch);
}
const int MAXN=40,MAXV=MAXN*MAXN*(MAXN+1)+5,MAXE=MAXV*2+MAXN*MAXN*2+5,INF=0x3f3f3f3f,dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int p,q,r,d,S,T;
int head[MAXV],ecnt=1;
struct EDGE{
    int v,w,nxt;
}e[MAXE<<1];
inline void add(const int& u,const int& v,const int& w){
    e[++ecnt].v=v;
    e[ecnt].w=w;
    e[ecnt].nxt=head[u];
    head[u]=ecnt;
}
inline void add_dual(const int& u,const int& v,const int& w){
    add(u,v,w);add(v,u,0);
}

int cur[MAXV],dep[MAXV];
inline bool bfs(){
    memset(dep,-1,sizeof(dep));
    queue<int>q;
    q.push(S);
    dep[S]=0;cur[S]=head[S];
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].v;
            if(e[i].w>0 && dep[v]==-1){
                q.push(v);
                cur[v]=head[v];
                dep[v]=dep[u]+1;
                if(v==T) return true;
            }
        }
    }
    return false;
}
int dfs(int u,int flow){
    if(u==T) return flow;
    int tmp,res=0;
    for(int i=cur[u];i && flow>0;i=e[i].nxt){
        cur[u]=i;
        int v=e[i].v;
        if(e[i].w>0 && dep[v]==dep[u]+1){
            tmp=dfs(v,min(flow,e[i].w));
            if(tmp==0) dep[v]=-1;
            e[i].w-=tmp;
            e[i^1].w+=tmp;
            res+=tmp;
            flow-=tmp;
        }
    }
    return res;
}
inline int dinic(){
    int res=0;
    while(bfs()) res+=dfs(S,INF);
    return res;
}

int main(){
    rd(p);rd(q);rd(r);rd(d);
    S=0;T=getid(p,q,r+1)+1;
    for(int k=1,val;k<=r;k++)
        for(int i=1;i<=p;i++)
            for(int j=1;j<=q;j++){
                rd(val);
                add_dual(getid(i,j,k),getid(i,j,k+1),val);
            }
    for(int i=1;i<=p;i++)
        for(int j=1;j<=q;j++){
            add_dual(S,getid(i,j,1),INF);
            add_dual(getid(i,j,r+1),T,INF);
        }
    for(int k=d+1;k<=r;k++)
        for(int i=1;i<=p;i++)
            for(int j=1;j<=q;j++)
                for(int dir=0;dir<4;dir++){
                    if(1<=i+dx[dir] && i+dx[dir]<=p && 1<=j+dy[dir] && j+dy[dir]<=q)
                        add_dual(getid(i,j,k),getid(i+dx[dir],j+dy[dir],k-d),INF);
                }
    wt(dinic(),'\n');
    return 0;
}

[ARC176E] Max Vector

Link

题意

给定两个长为 \(N\) 的序列 \(X,Y\)，还有 \(M\) 个长为 \(N\) 的序列 \(A_i\)。操作 \(M\) 次，每次要么让 \(X\) 和 \(A_i\) 分别每位取 \(\max\)，要么让 \(Y\) 和 \(A_i\) 分别每位取 \(\max\)，求 \(X,Y\) 最后所有元素之和最小值。

转化

正着去选择每个操作和谁取 \(\max\) 很难，可以反过来，找到一个最小的合法的 \(X,Y\)，满足 \(X\) 大于等于某些 \(A_i\)，而 \(Y\) 大于等于剩下的 \(A_i\)，此处的大于等于指的是对于两个等长序列，其中一个序列的元素每位都大于另一个序列的对应元素。

而合法的 \(X,Y\) 的判定标准为，对于每个 \(i\in[1,M]\)，如果 \(\exists j\) 使得 \(Y_j<A_{ij}\)，那么必须 \(\forall j\) 使得 \(X_j\geq A_{ij}\)。发现了吗，否则那么说明 \(\forall j\) 满足 \(Y_j\geq A_{ij}\)，也满足条件。发现了吗？这就类似我们之前推广的“如果 \(A_1\geq c_1\)，那么 \(A_2< c_2\)”的情况，于是我们对于 \(Y_j\) 得逆序取值。

但是我们怎么处理任意 \(Y_j\) 不大于等于就得全体 \(X_j\) 大于等于呢？我们增设一个虚点，将 \(Y_j\) 对应的 \(A_{ij}\) 全部连到这个虚点上，再由这个虚点连到全部 \(X_j\) 对应的 \(A_{ij}\) 上就可以了，如下图：

7

另外，由于本题的割代价是单调的（割的代价为割所代表取值本身），可以证明一条链上多于一个割是不优的，不需要连上文所述的反向边以保证每条链只有一个割。

代码 
#include<bits/stdc++.h>
#define getid(x,y) (((x)-1)*501+(y))
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar __getchar
inline char __getchar(){
    static char ch[1<<20],*l,*r;
    return (l==r&&(r=(l=ch)+fread(ch,1,1<<20,stdin),l==r))?EOF:*l++;
}
#endif
template<class T>inline void rd(T &x){
    T res=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while('0'<=ch && ch<='9'){res=res*10+ch-'0';ch=getchar();}
    x=res*f;
}
template<class T>inline void wt(T x,char endch='\0'){
    static char wtbuff[20];
    static int wtptr;
    if(x==0){
        putchar('0');
    }
    else{
        if(x<0){x=-x;putchar('-');}
        wtptr=0;
        while(x){wtbuff[wtptr++]=x%10+'0';x/=10;}
        while(wtptr--) putchar(wtbuff[wtptr]);
    }
    if(endch!='\0') putchar(endch);
}
const int MAXN=10,MAXM=500,MAXV=MAXN*2*(MAXM+1)+MAXM+100,MAXE=MAXN*2*(MAXM+2)+MAXM*MAXN*2+100,INF=0x3f3f3f3f;
int n,m,S,T,X[MAXN+2],Y[MAXN+2];
int head[MAXV],ecnt=1;
struct EDGE{
    int v,w,nxt;
}e[MAXE<<1];
inline void add(const int& u,const int& v,const int& w){
    e[++ecnt].v=v;
    e[ecnt].w=w;
    e[ecnt].nxt=head[u];
    head[u]=ecnt;
}
inline void add_dual(const int& u,const int& v,const int& w){
    add(u,v,w);add(v,u,0);
}

int cur[MAXV],dep[MAXV];
inline bool bfs(){
    memset(dep,-1,sizeof(dep));
    queue<int>q;
    q.push(S);
    dep[S]=0;cur[S]=head[S];
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].v;
            if(e[i].w>0 && dep[v]==-1){
                q.push(v);
                cur[v]=head[v];
                dep[v]=dep[u]+1;
                if(v==T) return true;
            }
        }
    }
    return false;
}
int dfs(int u,int flow){
    if(u==T) return flow;
    int tmp,res=0;
    for(int i=cur[u];i && flow>0;i=e[i].nxt){
        cur[u]=i;
        int v=e[i].v;
        if(e[i].w>0 && dep[v]==dep[u]+1){
            tmp=dfs(v,min(flow,e[i].w));
            if(tmp==0) dep[v]=-1;
            e[i].w-=tmp;
            e[i^1].w+=tmp;
            res+=tmp;
            flow-=tmp;
        }
    }
    return res;
}
inline int dinic(){
    int res=0;
    while(bfs()) res+=dfs(S,INF);
    return res;
}

int main(){
    rd(n);rd(m);
    S=0;T=n*2*501+m+1;
    for(int i=1;i<=n;i++) rd(X[i]);
    for(int i=1;i<=n;i++) rd(Y[i]);
    for(int i=1;i<=n;i++){
        add_dual(S,getid(i,X[i]),INF);
        for(int j=X[i];j<=500;j++) add_dual(getid(i,j),getid(i,j+1),j);
        add_dual(getid(i,501),T,INF);
    }
    for(int i=1;i<=n;i++){
        add_dual(S,getid(i+n,501),INF);
        for(int j=500;j>=Y[i];j--) add_dual(getid(i+n,j+1),getid(i+n,j),j);
        add_dual(getid(i+n,Y[i]),T,INF);
    }
    for(int k=n*2*501+1;k<=n*2*501+m;k++){
        for(int i=1,x;i<=n;i++){
            rd(x);
            add_dual(getid(i+n,x),k,INF);
            add_dual(k,getid(i,x),INF);
        }
    }
    wt(dinic(),'\n');
    return 0;
}

  1. 严格证明见https://www.luogu.com.cn/article/azy0pjrl的“本题的特殊性”部分。 ↩︎

标签：tmp,geq,return,int,res,最小,差分,dep,广义
From： https://www.cnblogs.com/SkyNet-PKN/p/18433249

相关文章

  • 差分约束
    差分约束系统参考博客：oiwiki博客园差分约束系统定义差分约束系统是一种特殊的\(n\)元一次不等式组，它包含\(n\)个变量\(x_1,x_2,\dots,x_n\)以及\(m\)个约束条件，每个约束条件是由两个其中的变量做差构成的，形如\(x_i-x_j\leqc_k\)，其中\(1\leqi,j\leqn,......
  • 数据结构——广义表
    广义表的概念    广义表（又称列表Lists）是n>=0个元素a0，a1，...，an-1的有限序列，其中每一个ai可以是原子，或者是一个广义表。广义表和线性表的区别：线性表的元素是单一的类型，而广义表的元素可以是不同类型，其元素也可以是一个广义表（子表）。广义表通常记作:LS=(a1，a2，...，an）   ......
  • c语言实现最小堆和最大堆
    第一部分：最大堆和最小堆的基本性质（1）基本定义①最大堆根是这颗树最大的值，每个根节点都比  左右子节点的值大，对左右子树仍然成立；②最小堆根是这颗树的最小的值，每个根节点都比左右子节点的值小，同样对左右子树成立；（2）性质（数组下标关系）由堆构建的树的背后原理是基于完全......
  • 远程升级频频失败？你可能忽略了模组差分包…
    去年开发的一个项目产品，用的是合宙4G-Cat.1低功耗模块Air780E。最近有客户反馈在乡村里频繁出现掉线的情况。通过换货、换SIM卡对比排查测试，发现只有去年5月22号采购的那批模块在客户环境附近会出现掉线的情况，而今年4月份采购的模块批次就不会掉线，很奇怪。我联系了对应负责的销售，了......
  • 亚诺德经典低失真差分ADC驱动器芯片——AD8138
    博主首拆华为三折叠MateXT：内部设计完胜iPhone16，零部件多是国产光刻机的“前世今生”推荐文章：本期是平台君和您分享的第78期内容NEWS新闻早知道今年的巴黎奥运会结束了，不仅是中国人，连无数外国人都情不自禁怀念起16年前的北京奥运会开幕式。在2008年，智能手机还没......
  • 基于 pandas DataFrame 中所有列的值的最小行计数条件
    假设我在pandasDataFrame中有三列，没有任何null或空值。每个项目的设施始终具有唯一的值。一个项目可以有一个或多个与其关联的供应商。同一供应商可以显示对于给定项目的不同设施，多次注册。对于给定项目，设施永远不会与多个供应商关联。......
  • 3170. 删除星号以后字典序最小的字符串
    题目链接3170.删除星号以后字典序最小的字符串思路堆栈&位运算题解链接三种写法：26个栈+位运算优化（Python/Java/C++/Go）关键点1.用堆栈跟踪各个字母出现的位置2.用位运算跟踪当前最小字母（lowbit技巧）时间复杂度朴素做法：\(O(n\vert\Sigma\vert)\)位运算......
  • 一维差分和等差数列差分
    一维差分不支持边操作边查询对于数组a，定义其差分数组（differencearray）为i=0时，d[i]=a[0];i>0时，d[i]=a[i]-a[i-1];性质1：从左到右累加d中的元素，可以得到数组a。性质2：如下两个操作是等价的。区间操作：把a的子数组a[i,j]都加上x。单点操作：把d[i......
  • 树上差分+lca 黑暗的锁链
    //**太久不写了，感觉很难受。。。比赛最近打得也不好，课内任务又重，还要忙着做项目。何去何从。今天又写了一题，用了树上差分的知识。下面来整理整理。1.首先让我们学一下lca（最小公共父节点） 我用的是倍增来求的。总共其实就是两步：dfs打ST表预处理每个点的上面节点 lca求两......
  • 76.最小覆盖子串 Golang实现
    题目描述：给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串，则返回空字符串""。注意：对于t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。如果s中存在这样的子串，我们保证它是唯一的答......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99