头像

人间温柔




离线:20小时前


最近来访(88)
用户头像
18910310021
用户头像
xiaozd
用户头像
Amaryllis_
用户头像
PseudorandomGenerators
用户头像
jiyunkun
用户头像
Latrix
用户头像
叔夜
用户头像
种花家的市长
用户头像
冰之韵
用户头像
十指相扣
用户头像
ctOS
用户头像
封禁用户
用户头像
zeta_y
用户头像
唇齿相依
用户头像
垫底抽風
用户头像
dp咋学啊
用户头像
四合院院士
用户头像
LeoDerek
用户头像
你一笑便是人间温柔
用户头像
whale77


学习笔记目录
有任何问题,欢迎私信/评论。
码字不易,求点赞啦~

最小割问题

根据我在 网络流的基本概念 中提出的概念,最小割就应该是所有割中,流量最小的一个。题目通常求的是最小割的容量。

有一个非常神奇的定理:最大流最小割定理,这个定理只有短短的几个字:最大流等于最小割。

关于定理的证明,其实我没太看懂,但我个人的直观理解就是:最小割限制了整个网络的流的上界,所以就有最大流等于最小割。

因此,求解最小割就变得很简单了,只需要套用最大流的 $dinic$ 算法就可以求解了。




学习笔记目录
有任何问题,欢迎私信/评论。
码字不易,求点赞啦~

最大流问题

求一个网络中,最多能有多少个单位的流量能从源点流向汇点。————这就是最大流问题。

求解最大流问题有两大主要算法:$EK$ 算法和 $dinic$ 算法。

$EK$ 算法

$EK$ 算法也叫动能算法($E_K$)。

利用一下贪心的思想,可以发现:只要残量网络中存在增广路,流量就可以增大;如果残量网络中已经没有增广路了,那么当前求得的流就是最大流。这个就是著名的 增广路定理

$EK$ 算法就利用了增广路定理,每次 $bfs$ 会沿着最短增广路(也就是边数最少的增广路)进行增广。那么这一条增广路对答案的贡献就是所有弧上残量的最小值。

记这当前增广路所有弧上残量的最小值为 $mn$。那么需要把正向弧的残量减去 $mn$,反向弧的流量加上 $mn$。

$EK$ 算法代码:

#include<bits/stdc++.h>
using namespace std;

const int maxn=200;                             //点数 
const int maxm=400;                             //边数(由于有反向弧,所以要乘以2,具体数值看题目的数据范围) 
const long long inf=0x3f3f3f3f;

struct edge {
    int fr,to,nxt;
    long long c;                                //一条边的流量 
}e[maxm];
int n,m,s,t;
int cnt=1;
int head[maxn];

void add_edge(int u,int v,long long c){
    cnt++;
    e[cnt].fr=u;
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    e[cnt].c=c;
    head[u]=cnt;
}

int pre[maxn];

void bfs(){                                     //bfs 寻找一条最短增广路 
    queue<int>q;
    q.push(s);
    memset(pre,-1,sizeof(pre));
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(pre[v]==-1 && e[i].c){
                pre[v]=i;
                if(v==t){
                    break;
                }
                q.push(v);
            }
        }
        if(pre[t]!=-1){
            break;
        }
    }
}

long long EK(){                                 //将 bfs 中找到增广路上的所有流量进行修改 
    long long ret=0;
    while(1){
        bfs();
        if(pre[t]==-1){
            break;
        }
        long long Min_c=inf;
        for(int u=t;u!=s;u=e[pre[u]].fr){
            Min_c=min(Min_c,e[pre[u]].c);       //找出所有弧中的最小流量 
        }
        for(int u=t;u!=s;u=e[pre[u]].fr){
            e[pre[u]].c-=Min_c;                 //正向弧减去最小流量 
            e[pre[u]^1].c+=Min_c;               //反向弧加上最小流量。这里利用了奇数^1=偶数,偶数^1=奇数的原理,能够保证(2,3)(3,4)等组成一组。 
        }
        ret+=Min_c;
    }
    return ret;
}

int main(){
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        int u,v;
        long long flow;
        cin>>u>>v>>flow;
        add_edge(u,v,flow);
        add_edge(v,u,0);
    }
    cout<<EK()<<endl;
    return 0;
}

$dinic$ 算法

$dinic$ 算法与 $EK$ 算法类似,也是不停的寻找增广路。但是 $EK$ 算法是一条一条地找增广路,效率太过低下。$dinic$ 算法会利用分层的思想,一次性找出多条增广路(注意不是所有),提高效率。

  1. $dinic$ 算法会构建分层图,按照层次关系增广。每一次对源点进行 $bfs$,对每个节点按照层次编号。

  2. $dfs$ 进行多路增广。$EK$ 算法一次只会增广一条路径,$dinic$ 通过 $dfs$ 能同时找到多条增广路。
    为什么需要进行分层?

分层,就能够流量只会从低层次的节点往高层次的节点走(也就是相邻的两层),而不会出现回流的情况。因为一旦回流,$dfs$ 就会陷入死循环。

$dinic$ 算法代码:

#include<bits/stdc++.h>
using namespace std;

const int maxn=205;
const int maxm=5005;
const long long inf=50010000000000;

int n,m,s,t;

struct edge{
    int fr,to,nxt;
    long long c;
}e[maxm<<1];
int head[maxn],cnt=1;
int dep[maxn];//dep[u] 代表节点 u 所在的层 
int q[maxn],l,r;

void add_edge(int u,int v,int c){
    cnt++;
    e[cnt].fr=u;
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    e[cnt].c=c;
    head[u]=cnt;
}

bool bfs(){
    l=1; r=0;
    q[++r]=s;
    memset(dep,0,sizeof(dep));
    dep[s]=1;
    while(l<=r){
        int u=q[l];
        l++;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(e[i].c>0 && dep[v]==0){//如果一条边还有流量,且点未被分层,就需要将他分层 
                q[++r]=v;
                dep[v]=dep[u]+1;
            }
        }
    }
    if(dep[t]==0) return false;
    return true;
}

long long dfs(int u,long long flow){
    if(u==t) return flow;
    long long tot=0;
    for(int i=head[u];i && flow;i=e[i].nxt){
        int v=e[i].to;
        if(e[i].c>0 && dep[v]==dep[u]+1){
            long long res=dfs(v,min(flow,e[i].c));
            e[i].c-=res;
            e[i^1].c+=res;
            tot+=res;
            flow-=res;
            if(flow==0){
                break;
            }
        }
    }
    if(tot==0){
        dep[u]=0;
    }
    return tot;
}

long long dinic(){
    long long ret=0;
    while(bfs()){
        ret+=dfs(s,inf);
    }
    return ret;
}

int main(){
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        int u,v,c;
        cin>>u>>v>>c;
        add_edge(u,v,c);
        add_edge(v,u,0);
    }
    cout<<dinic()<<endl;
    return 0;
}


新鲜事 原文

AcWing【集日历瓜分10000AC币活动】求1月日历!https://www.acwing.com/file_system/gui/taskbar/widgets/clock/calendar/receive/113030/1/


新鲜事 原文

AcWing【集日历瓜分10000AC币活动】求5月日历!https://www.acwing.com/file_system/gui/taskbar/widgets/clock/calendar/receive/113030/5/



人间温柔
3个月前

从题目中 $1->2,2->3,3->1,4->5,5->4,6->6$ 的对应关系中,我们发现它实际上是对应了三个环,节点个数分别为 $3,2,1$。所以要让 $1,2,3,4,5,6$ 的排列出现循环,就要进行 $\text{lcm}(3,2,1)=6$ 步操作,算上原序列本身,就是 $7$ 行。

要求不同的 $\text{lcm}$ 的个数,所以问题转换成:将 $n$ 拆分成若干个正整数的和,求这些正整数不同最小公倍数的个数。

只要数字之间互质,那么他们的 $\text{lcm}$ 每次都是不同的。

如何使得这些数字互质?

只要他们能够表示成不同质数的幂 $p^k(k\in N,p^k \leq n)$ 就可以。可以选择的质数 $p \in [2,n]$,又要满足 $p^k \leq n(k\in N)$,

我们对 $0$ 次幂特别处理一下,$p^0=1$,如果现在有一个和为小于 $n$ 的方案,那么增加若干 $1$ 以后总能够变成 $n$,且 $1$ 的加入不会影响最终的 $\text{lcm}$。所以我们可以把 $0$ 次幂忽略。

于是最终的题目可以转换成求 $\sum_{i=1}^{n}(\text{总和等于}\ i \ \text{的方案数})$。

额,这不就是完全背包嘛?于是乎,这道题就这么做完了。

胡!

#include<bits/stdc++.h>
using namespace std;

const int maxn=1005;

int n;
int prime[maxn],flag[maxn],cnt=0;//和质数有关的一些变量
long long f[maxn];//f[i] 表示总和等于 i 时的方案数。

void get_prime(){//由于数据范围很小,这里就用埃氏筛了(当然用欧拉筛也可以)(当然想用 Min25 筛我了不拦着o(* ̄▽ ̄*)ブ)
    for(int i=2;i<=n;i++){
        if(flag[i]==false){
            prime[++cnt]=i;
            for(int j=2*i;j<=n;j+=i){
                flag[j]=true;
            }
        }
    }
}

int main(){
    cin>>n;
    get_prime();
    f[0]=1;
    for(int i=1;i<=cnt;i++){//枚举出质数
        for(int j=n;j>=prime[i];j--){//枚举总和
            for(int k=prime[i];k<=j;k*=prime[i]){//这里的 k 就是质数 p 的幂。
                f[j]+=f[j-k];
            }
        }
    }
    long long ans=0;
    for(int i=0;i<=n;i++){
        ans+=f[i];
    }
    cout<<ans<<endl;
    return 0;
}


新鲜事 原文

人间温柔
4个月前
CSP-S rp++



人间温柔
5个月前

01背包能不能输出哪些物品被选中了




人间温柔
6个月前

题目要求区间 $[x,y]$ 和 $[m,n]$ 一模一样,我就考虑到了并查集。

$\forall\ i\in [x,y]$ 以及 $i$ 在 $[m,n]$ 中对应的格子,我们把这两个格子连边,这样经过若干次连便之后,凡是处在同一个联通块中的格子,取的数字必须是相等的。

如果目前得到了 $k$ 个连通块,则答案就等于 $9\times 10^{k-1}$。有 $1$ 在的那个连通块只能取 $1 \sim 9$ 这九个数字,而其他的 $k-1$ 个连通块可以取 $0\sim 10$ 这十个数字,根据乘法原理便可证明上式的正确性。

但是看一看数据范围,我们发现如果一条边一条边的连,早就 $TLE$ 了。

利用倍增的思想,我们考虑区间并查集。$f[i][j]$ 表示的含义是:以 $i$ 为左端点,长度为 $2^j$ 的一个区间。为了方便描述,我们令 $x=1,y=13,m=20,n=32$。这样两个区间,可以按照下图进行分割:

$merge$ 是并查集中的连边操作函数,那么我们在分割完区间之后需要进行的操作是:

merge{f[1][3],f[20][3]};
merge{f[9][2],f[28][2]};
merge{f[13][0],f[32][0]};

然后利用并查集统计答案。

记得要开 $long\ long$ 哦!

#include<bits/stdc++.h>
using namespace std;

const int mod=1e9+7;
const int maxn=100005;

long long ans=1;
int n,m;
int f[maxn][20]; //f[i][j]:[i,j] --> id,他表示的含义是 [i,j] 区间所对应的编号 
int id;          //用于给区间编号 
int fa[maxn*20];
int s[maxn*20]; //s[i]:编号为 i 的区间的左端点 

void build(){
    for(int j=0;j<=log2(n);j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=++id;
            fa[id]=id;
            s[id]=i;
        }
    }
}

int find(int x){
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}

void merge(int l1,int l2,int k){
    int p=find(f[l1][k]),q=find(f[l2][k]);
    if(p>q){
        swap(p,q);
    }
    fa[q]=p;
}

int main(){
    cin>>n>>m;
    build();
    for(int i=1;i<=m;i++){
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        for(int k=log2(r1-l1+1);k>=0;k--){
            if(l1+(1<<k)-1<=r1){
                merge(l1,l2,k);  //合并区间 [l1,k] & [l2,k]
                l1+=(1<<k);
                l2+=(1<<k);
            }
        }
    }
    for(int k=log2(n);k>0;k--){
        for(int i=1;i+(1<<k)-1<=n;i++){
            int pa=find(f[i][k]);
            int spa=s[pa];      //pa 区间的左端点 
            merge(spa,i,k-1);
            merge(spa+(1<<k-1),i+(1<<k-1),k-1);
        }
    }
    for(int i=2;i<=n;i++){          //注意 i 从 2 开始,因为 f[1][0] 代表的是 1 所在的那个连通块,而这个连通块是需要乘以 9 的,并不需要乘以 10,所以会放在输出的时候特殊处理 
        if(f[i][0]==find(f[i][0])){ //这个判断结果如果为真,那么就是找到了一个连通块,ans需要乘以 10 
            ans=ans*10ll%mod;
        }
    }
    cout<<ans*9%mod<<endl;
    return 0;
}



人间温柔
6个月前

想问一下,treap 的旋转是如何进行的,最好是能够用动图直观展示,谢谢大佬!




人间温柔
7个月前

为了方便分析问题,我们假设 $n=3$。数字 $1\sim 3$ 总共有 $n!=6$ 种排列。则:
$$
k=1时,有这几种排列情况\begin{cases}
1,2,3
\end{cases}
$$
$$
k=1时,有这几种排列情况\begin{cases}
1,3,2\
2,1,3
\end{cases}
$$
$$
k=2时,有这几种排列情况\begin{cases}
2,3,1\
3,1,2
\end{cases}
$$
$$
k=3时,有这几种排列情况\begin{cases}
3,2,1
\end{cases}
$$
以 $k=2,k-1=1$ 两个例子来举例,画出如下的图:
图1.png
同行比较的话,可以发现,欲使逆序对的数量减少 $1$,只需要把 $n$ 这个数与它后一个数交换位置即可。反过来也一样,欲使逆序对的数量增加 $1$,只需要把 $n$ 这个数与它前一个数交换位置即可。也就是说红色集合圈与绿色集合圈实现了一个相互映射:
a.png

这又引出了另一个问题:如果 $n$ 在第一位,或者最后一位,那它就无法与它后一个数或者前一个数交换位置。

因此,$n$ 在第一位,或者最后一位的情况时无法参与到映射中的。根据数学知识,$n$ 在第一位是包含于红色集合圈的,$n$ 在最后一位也是包含于绿色集合圈的,这两种情况需要排除,也就是下图中紫色蓝色集合圈不参与映射:
a.png

现在有了这些分析,我们开始推到递推方程。假设 $f[n][k]$ 代表的含义是 $1,2,\ldots n$ 的所有排列中,逆序对数量等于 $k$ 的方案数。

在左图中,真正参与的是红色集合圈减去紫色集合圈,也就是 $f[n][k]-f[n-1][k]$。因为 $n$ 是最大数,放在最后一位对逆序对的贡献是 $0$,也就是说我们只需要满足 $n$ 之前由 $1,2,\ldots n-1$ 组成的排列中逆序对的数量等于 $k$,所以紫色集合圈就是 $f[n-1][k]$。

同理,右图中真正参与的是绿色集合圈减去蓝色集合圈,也就是 $f[n][k-1]-f[n-1][k-n]$。当 $n$ 在第一位时,它大于后面所有的 $n-1$ 个数,所以对逆序对数量的贡献是 $n-1$,也就是说我们只需要满足 $n$ 之前由 $1,2,\ldots n-1$ 组成的排列中逆序对的数量等于 $k-1-(n-1)=k-n$即可,所以蓝色集合圈就是 $f[n-1][k-n]$。

既然两者数量上相等,所以等式 $f[n][k]-f[n-1][k]=f[n][k-1]-f[n-1][k-n]$ 就成立,通过移项,就是:
$$
f[n][k]=f[n][k-1]+f[n-1][k]-f[n-1][k-n]
$$
这就是最后的递推方程。

$AC$ 代码如下:

#include<bits/stdc++.h>
using namespace std;

const int mod=1000000007;
const int maxn=1005;
const int maxk=10005;

int n,k;
bool mem_flag[maxn][maxk];
int mem[maxn][maxk];

long long f(int n,int k){
    if(k<0) return 0;
    if(n==0 && k==0) return 1;
    if(n==0 && k>0) return 0;
    if(mem_flag[n][k]) return mem[n][k];

    long long ret=f(n-1,k)+f(n,k-1)-f(n-1,k-n);
    ret%=mod;
    mem_flag[n][k]=true;
    return mem[n][k]=ret;
}

int main(){
    scanf("%d%d",&n,&k);
    printf("%d\n",(f(n,k)+mod)%mod);
    return 0;
}