欧拉路

有向图欧拉路径：有且仅有一个终点入度比出度多1 有且仅有一个起点出度比入度多1 有向图欧拉回路：所有点出入度相等 无向图欧拉路径：有且仅有两个点度数为奇数 无向图欧拉回路：所有点度数相等

void Dfs(int u) 
{
    for(int &i=cur[u];i<e[u].size();) Dfs(e[u][i++]);
    stk[++top]=u;
}

二分图

• 在二分图中： $|最大匹配|=|最小点覆盖|=a$ $|最小边覆盖|=|最大独立集|=b$ $a+b=|点集|$
• 二分图判定

1. 染色判定
2. 无奇环是一个图是二分图的充要条件

• 匈牙利算法 时间复杂度$O(nm)$

int Dfs(int u)
{
    for(int v:e[u])
    {
        if(vis[v]) continue;
        vis[v]=1;
        if(!match[v] || Dfs(match[v])) {match[v]=u; return 1;}
    }
    return 0;
}

网络流

![[Pasted image 20250102144046.png]]

• Dinic 时间复杂度$O(n^2m)$ 单位网络复杂度 $O(\sqrt{ n }m)$

/**
 * @file    :work.cpp
 * @author  :yeyou26
 * @date    :2025-01-02 14:29:05
 */
#include <bits/stdc++.h>
using std::cerr;using std::cout;using std::cin;using std::endl;
#define pb push_back
#define int long long
const int N = 205;
const int M = 5005;
struct edge
{
    int v,w,nxt;
}e[M*2];
int n,m,S,T,eid=1,dep[N],q[N],frt,tal,head[N],cur[N],vis[N];
void adde(int u,int v,int w)
{
    e[++eid].v=v,e[eid].w=w,e[eid].nxt=head[u],head[u]=eid;
    e[++eid].v=u,e[eid].w=0,e[eid].nxt=head[v],head[v]=eid;
}
int bfs()
{
    frt=tal=0;
    for(int i=1;i<=n;i++) cur[i]=head[i],dep[i]=-1;
    q[tal=1]=S,dep[S]=0;
    while(frt!=tal)
    {
        int u=q[++frt];
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v = e[i].v,w = e[i].w;
            if(!w || dep[v]!=-1) continue;
            dep[v]=dep[u]+1,q[++tal]=v;
        }
    }
    return dep[T]!=-1;
}
int dinic(int u,int lft)
{
    if(u==T || !lft) return lft;
    int sum=0;
    for(int &i=cur[u];i;i=e[i].nxt)
    {
        int v = e[i].v,w=e[i].w;
        if(dep[v]!=dep[u]+1) continue;
        int t = dinic(v,std::min(lft,w));
        e[i].w-=t,e[i^1].w+=t,sum+=t,lft-=t;
        if(!lft) break;
    }
    if(sum==0) dep[u]=-1;
    return sum;
}
signed main()
{
    std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    cin>>n>>m>>S>>T;
    for(int i=1;i<=m;i++)
    {
        int u,v,w; cin>>u>>v>>w;
        adde(u,v,w);
    }
    int ans=0;
    while(bfs()) ans+=dinic(S,INT_MAX/2);
    cout<<ans<<'\n';
    return 0;
}

• DAG最小不可重链覆盖 把所有结点i拆为结点i和结点′i ，如果图G中存在有向边i⇒j，则在二分图中引入边i⇒′j 。设二分图的最大匹配数为m，则结果就是n−m。为什么呢？因为匹配和链覆盖是一一对应的。对于链覆盖中的每条链，除了最后一个“结尾结点”之外都有唯一的后继与它对应（即匹配结点），因此匹配数就是非结尾结点的个数。当匹配数达到最大时，非结尾结点的个数也将达到最大。此时，结尾结点的个数最少，即链条数最少
• DAG最小可重链覆盖 我们一般先用Floyd求原图的传递闭包，接着求这个闭包偏序集的最小不可重链覆盖

上下界网络流

无源汇可行流

• 所有边强行流跑到下界，类似预流推进的感觉，统计每个点的超额/缺失流量，显然 $\sum \text{ 超额流量}=\sum \text{ 缺失流量}$，建立新流量网络 $G'$，流量为$\text{原上界~-~原下界}$
• 临时源 $SS$ 向超额点连边，缺失点向临时汇 $TT$ 连边，对 $SS-TT$ 跑最大流，若最大流等于超额/缺失流量，则问题有解，当前网络为一组可行解

有源汇可行流

• $T$ 向 $S$ 连容量为 $\infty$ 的边，然后无源汇可行流，答案为 $Capcity(invE_{T\to S})$

有源汇最小/大流

• 先有源汇可行流，然后撤掉 $T\to S,SS,TT$
• 最小流：$T\to S$ 跑最大流，从可行流中减掉
• 最大流：$S\to T$ 跑最大流，从可行流中加上

费用流

• zkw 费用流

/**
 * @file    :work.cpp
 * @author  :yeyou26
 * @date    :2025-01-02 14:29:05
 */
#include <bits/stdc++.h>
using std::cerr;using std::cout;using std::cin;using std::endl;
#define pb push_back
#define int long long
const int N = 5005;
const int M = 100050;
struct edge
{
    int v,w,c,nxt;
}e[M*2];
int n,m,S,T,eid=1,d[N],head[N],cur[N],vis[N],inq[N];
void adde(int u,int v,int w,int c)
{
    e[++eid].v=v,e[eid].w=w,e[eid].nxt=head[u],head[u]=eid,e[eid].c=c;
    e[++eid].v=u,e[eid].w=0,e[eid].nxt=head[v],head[v]=eid,e[eid].c=-c;
}
int spfa()
{
    std::queue<int> q;
    for(int i=1;i<=n;i++) d[i]=LLONG_MAX/2,cur[i]=head[i];
    d[S]=0,q.push(S),inq[S]=1;
    while(q.size())
    {
        int u=q.front(); inq[u]=0; q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v = e[i].v,w=e[i].w,c=e[i].c;
            if(w && d[v]>d[u]+c) 
            {
                d[v]=d[u]+c;
                if(!inq[v]) inq[v]=1,q.push(v);
            }
        }
    }
    return d[T]!=LLONG_MAX/2;
}
int dinic(int u,int lft)
{
    if(u==T || !lft) return lft;
    int sum=0; 
    vis[u]=1;
    for(int &i=cur[u];i;i=e[i].nxt)
    {
        int v = e[i].v,w=e[i].w;
        if(d[v]!=d[u]+e[i].c || vis[v]) continue;
        int t = dinic(v,std::min(lft,w));
        e[i].w-=t,e[i^1].w+=t,sum+=t,lft-=t;
        if(!lft) break;
    }
    vis[u]=0;
    if(sum==0) d[u]=LLONG_MAX/2;
    return sum;
}
signed main()
{
    std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    cin>>n>>m>>S>>T;
    for(int i=1;i<=m;i++)
    {
        int u,v,w,c; cin>>u>>v>>w>>c;
        adde(u,v,w,c);
    }
    int ans=0,cost=0,t;
    while(spfa()) t=dinic(S,LLONG_MAX/2),ans+=t,cost+=d[T]*t;
    cout<<ans<<' '<<cost<<'\n';
    return 0;
}

联通性问题

点双连通分量

两点简单路径并等于经过点双并

命题

在无向图 ( G = (V, E) ) 中，设 ( s ) 和 ( f ) 是两个不同的顶点。 则从 ( s ) 到 ( f ) 的所有简单路径的并集等于从 ( s ) 到 ( f ) 的所有路径所经过的双连通分量的并集

证明

1. 从简单路径的并集包含在双连通分量的并集内

• 任取从 ( s ) 到 ( f ) 的一条简单路径 ( P )。
• 路径 ( P ) 是连通的，因此其中的每个子路径都位于某个连通分量内。
• 进一步地，由于 ( P ) 是简单路径，路径上的每两个连续边不构成割点，因此路径 ( P ) 所经过的每个部分至少位于某个双连通分量中。
• 因此，路径 ( P ) 上的所有顶点和边都属于某些双连通分量，这些双连通分量被至少一条从 ( s ) 到 ( f ) 的简单路径所经过。
• 综上，所有简单路径的并集中的顶点和边都包含在从 ( s ) 到 ( f ) 的所有路径所经过的双连通分量的并集内。

2. 从双连通分量的并集包含在简单路径的并集内

• 任取一个双连通分量 ( B )，假设存在一条从 ( s ) 到 ( f ) 的简单路径 ( P ) 经过 ( B )。
• 由于 ( B ) 是双连通的，任意两个顶点在 ( B ) 内都有至少两条不共享内部顶点的路径连接。
• 这意味着，在 ( B ) 内，可以通过不同的路径穿行，而不会导致路径 ( P ) 出现割点。
• 因此，( B ) 内的所有顶点和边都可以在至少一条从 ( s ) 到 ( f ) 的简单路径上被访问。
• 因此，双连通分量 ( B ) 内的所有顶点和边都包含在从 ( s ) 到 ( f ) 的某些简单路径的并集中。

2-SAT

• 基本 $i->j$ 这样的连边代表如果选 $i$ 一定选 $j$ 显然我们有以下结论: 1.若有$i->j$ 则有 $j'->i'$ 2.若有$i->j \quad j->k$ 则有 $i->k$ 3.若 $i,i'$ 在同一个SCC中，则无解 4.Tarjan求得的SCC的编号为拓扑逆序
• 约束条件及常见连边 设变量 $xi,xj$，$i,j$ 表示变量取正值，$i',j'$ 表示变量取反值 1.$xi$ 必为真 连边 $i'->i$ 2.$xi$ 必为假 连边 $i->i'$ 3.$xi与xj$ 至少有一个为真 连边 $i'->j \quad j'->i$ 4.$xi与xj$ 至少有一个为假 连边 $i->j' \quad j->i'$ 5.$xi与xj$ 相同 连边 $i->j \quad j->i \quad i'->j' \quad j'->i'$ 6.$xi与xj$ 不同 连边 $i->j' \quad j->i' \quad i'->j \quad j'->i$
• 判定及构造解 解的判定：如果不存在 $i,i'$ 在同一个SCC中，则一定有解，否则无解 构造解：对于每个布尔变量，检查它正反变量所在的SCC，把SCC编号小的点置为真

圆方树

构建

• 在圆方树中，原图的每个点对应一个圆点，每一个点双连通分量对应一个方点。
• 共有 $n+c$ 个点，其中 $n$ 是原图点数，$c$ 是原图点双连通分量的个数。 而对于每一个点双连通分量，它对应的方点向这个点双连通分量中的每个点连边。
• 注意，多数情况下一个孤立点也被认为是一个点双连通分量，但是在圆方树中它只是一个孤立的圆点，需要具体情况具体分析。 ![[Pasted image 20241206233159.png]]

性质

• 同一个点双中的两点 $u,v$ 之间，一定存在一条简单路径，经过给定的在同一个点双内的另一点 $w$。
• 对于两个点 $u,v$，它们在原图中所有简单路径经过的点集之并，等于圆方树路径上经过所有方点的相邻圆点集合。