学习笔记目录
有任何问题，欢迎私信/评论。
码字不易，求点赞啦~
最大流问题
求一个网络中，最多能有多少个单位的流量能从源点流向汇点。————这就是最大流问题。
求解最大流问题有两大主要算法：$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$ 算法会利用分层的思想，一次性找出多条增广路（注意不是所有），提高效率。
-
$dinic$ 算法会构建分层图，按照层次关系增广。每一次对源点进行 $bfs$，对每个节点按照层次编号。
-
$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;
}
从题目中 $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;
}
题目要求区间 $[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;
}
为了方便分析问题，我们假设 $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$，只需要把 $n$ 这个数与它后一个数交换位置即可。反过来也一样，欲使逆序对的数量增加 $1$，只需要把 $n$ 这个数与它前一个数交换位置即可。也就是说红色集合圈与绿色集合圈实现了一个相互映射：
这又引出了另一个问题：如果 $n$ 在第一位，或者最后一位，那它就无法与它后一个数或者前一个数交换位置。
因此，$n$ 在第一位，或者最后一位的情况时无法参与到映射中的。根据数学知识，$n$ 在第一位是包含于红色集合圈的，$n$ 在最后一位也是包含于绿色集合圈的，这两种情况需要排除，也就是下图中紫色蓝色集合圈不参与映射：
现在有了这些分析，我们开始推到递推方程。假设 $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;
}
