yeyou26 的博客
关于图论的一切
yeyou26 LV 5 @ 2024-2-16 21:54:25

以下N表示点数 M表示边数 V表示点集 E表示边集 G表示图

存图

邻接表

int edgeid,head[N];
struct edge{int v,nxt,w;}e[2*M];

邻接矩阵

int g[N][N];

边集

struct edge{int u,v,w;}e[M];

最小生成树

Kruskal

时间复杂度 $O(m\log{m})$

算法流程

1.边集存图 2.按权值排序 3.贪心拿权值最小的边，并查集保证无环

注意

1.用并查集一定一定要记得初始化 2.图可能不是联通的，需要判断一下

code

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

const int N = 5005, M = (int)2e5+5;

struct edge{int u,v,w;}e[M];
int fa[N],sum,n,m;

int Find(int x){return fa[x]==x ? x : fa[x]=Find(fa[x]);}
void Union(int x,int y){if(Find(x)!=Find(y)) fa[Find(y)]=Find(x);}

bool cmp(edge x,edge y){return x.w<y.w;}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    sort(e+1,e+1+m,cmp);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1,cnt=0;i<=m;i++)
    {
        if(cnt>=n-1) break;
        if(Find(e[i].u)!=Find(e[i].v))
        {
            cnt++;
            Union(e[i].u,e[i].v);
            sum+=e[i].w;
        }
    }
    int check=0;
    for(int i=1;i<=n;i++) if(fa[i]==i) check++;
    if(check==1) cout<<sum;
    else cout<<"orz";
    return 0;
}

Prim

时间复杂度 $O(m\log{m})$

算法流程

1.把点分成在树中和不在树中 2.选择不在树中距离树最近的点加入树中并更新 3.重复2直到达到跳出条件

注意

1.重载运算符小于号要反着写

code

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

const int N = 5005;
const int M = (int)2e5+5;

int n,m,dis[N],vis[N],sum,cnt;

int edgeid,head[N];
struct edge{int v,nxt,w;}e[M*2];
void addedge(int u,int v,int w){edgeid++;e[edgeid].v=v;e[edgeid].w=w;e[edgeid].nxt=head[u];head[u]=edgeid;}

struct node{int id,d;};
priority_queue<node> pq;
bool operator<(node x,node y) {return x.d>y.d;} 

void Prim()
{
    for(int i=1;i<=n;i++) dis[i]=0x3f3f3f3f;
    dis[1]=0;
    pq.push((node){1,0});
    while(!pq.empty() && cnt<n)
    {
        node x=pq.top();
        pq.pop();
        int u=x.id;
        if(!vis[u])
        {
            vis[u]=1;
            cnt++;
            sum+=dis[u];
            for(int i=head[u];i;i=e[i].nxt)
            {
                int v=e[i].v;
                if(dis[v]>e[i].w && !vis[v]) {dis[v]=e[i].w;pq.push((node){v,dis[v]});}
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;addedge(u,v,w);addedge(v,u,w);}
    Prim();
    if(cnt!=n){cout<<"orz";return 0;}
    cout<<sum;
    return 0;
}

最短路

Dijkstra

时间复杂度 $O(m\log{m})$

算法流程

1.把点分为已求出最短路和未求出最短路 2.找到未求出最短路且距离已求出最短路的点最近的点加入最短路并更新 3.重复2直到堆空

code

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

#define ll long long
const int N = (int)1e5+5;
const int M = (int)2e5+5;
int n,m,st;
ll dis[N];

int edgeid,head[N];
bool vis[N];
struct edge{int v,w,nxt;}e[M*2];
void addedge(int u,int v,int w){edgeid++;e[edgeid].v=v;e[edgeid].w=w;e[edgeid].nxt=head[u];head[u]=edgeid;}

struct node {int id;ll d;};
bool operator<(node x,node y){return x.d>y.d;}
priority_queue<node> pq;

void Dij()
{
    for(int i=1;i<=n;i++) dis[i]=0x3f3f3f3f3f3f3f3f;
    dis[st]=0;
    pq.push((node){st,0});
    while(!pq.empty())
    {
        if(vis[pq.top().id]) {pq.pop();continue;}
        int u=pq.top().id;  pq.pop();
        vis[u]=1;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].w) 
            {
                dis[v]=dis[u]+e[i].w;
                pq.push((node){v,dis[v]});
            }
        } 
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>st;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        addedge(u,v,w);
    }
    Dij();
    for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
    return 0;
}

Spfa

时间复杂度 $O(km)$ (死了)

算法流程

1.把可能引起松弛操作的边加入队列 2.进行松弛操作 3.重复12直到队空

code

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

#define ll long long
const int N = (int)1e4+4;
const int M = (int)5e5+5;

int edgeid,head[N];
struct edge{int v,nxt,w;}e[M*2];
void addedge(int u,int v,int w){edgeid++;e[edgeid].v=v;e[edgeid].w=w;e[edgeid].nxt=head[u];head[u]=edgeid;}

int n,m,st;
bool inq[N];
ll dis[N];

deque<int> q;
void Spfa()
{
    for(int i=1;i<=n;i++) dis[i]=0x3f3f3f3f3f3f3f3f;
    dis[st]=0;
    q.push_front(st);
    inq[st]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop_front();
        inq[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].w)
            {
                dis[v]=dis[u]+e[i].w;
                if(!inq[v])
                {
                    if(!q.empty() && dis[v]<dis[q.front()]) q.push_front(v);
                    else q.push_back(v);
                    inq[v]=1;
                } 
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>st;
    for(int i=1;i<=m;i++) {int u,v,w;cin>>u>>v>>w;addedge(u,v,w);}
    Spfa();
    for(int i=1;i<=n;i++)
    {
        if(dis[i]!=0x3f3f3f3f3f3f3f3f) cout<<dis[i]<<" ";
        else cout<<INT_MAX<<" ";
    }
    return 0;
}

Floyd

时间复杂度 $O(n^3)$

算法流程

1.dp 2.三重for 依次枚举i,j,k g[i][j]=min(g[i][j],g[i][k]+g[k][j])

code

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

const int N = 105;

int g[N][N],n,m;

void Floyd()
{
    for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=(int)1e9;
    for(int i=1;i<=n;i++) g[i][i]=0;
    for(int i=1;i<=m;i++) {int u,v,w;cin>>u>>v>>w;g[u][v]=min(g[u][v],w);g[v][u]=min(g[v][u],w);}
    Floyd();
    for(int i=1;i<=n;i++) 
    {
        for(int j=1;j<=n;j++) cout<<g[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

Johnson

时间复杂度 $O(nm\log{m})$

算法流程（极简版）

1.超级源点向外连边，SPFA求势能 2.改边 3.每个点跑Dijkstra

code

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


const int INF = (int)1e9;
const int N =(int)3e3+3;
const int M =(int)6e3+4;

struct bian{int u,v,w;} b[M*2];

struct node{int id,v;};
bool operator<(node x,node y){return x.v>y.v;}

int eid,head[N],h[N],vis[N],inq[N],d[N],n,m;
priority_queue<node> pq;
queue<int> q;
struct edge{int v,nxt,w;}e[M*2];
void addedge(int u,int v,int w)
{
    eid++;
    e[eid].v=v;
    e[eid].w=w;
    e[eid].nxt=head[u];
    head[u]=eid;
}

bool Spfa()
{
    for(int i=1;i<=n;i++) h[i]=INF;
    q.push(0);
    inq[0]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        inq[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(h[v]>h[u]+e[i].w)
            {
                h[v]=h[u]+e[i].w;
                if(!inq[v])
                {
                    inq[v]=1;
                    q.push(v);
                    vis[v]++;
                    if(vis[v]>=n+1) return 0;
                }
            }
        }
    }
    return 1;
}

void Dijkstra(int st)
{
    for(int i=1;i<=n;i++) d[i]=INF,vis[i]=0;
    d[st]=0;
    pq.push((node){st,0});
    while(!pq.empty())
    {
        int u=pq.top().id;
        pq.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(d[v]>d[u]+e[i].w)    
            {
                d[v]=d[u]+e[i].w;
                if(!vis[v]) pq.push((node){v,d[v]});
            }
        }
    }
    return ;
}

signed main()
{
    // freopen("working.in","r",stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        addedge(u,v,w);
    }
    for(int i=1;i<=n;i++) addedge(0,i,0);
    if(!Spfa())
    {
        cout<<-1;
        return 0;
    }
    for(int k=1;k<=n;k++) 
    {
        for(int i=head[k];i;i=e[i].nxt) e[i].w=e[i].w+h[k]-h[e[i].v];
    }
    for(int i=1;i<=n;i++)
    {
        long long sum=0;
        Dijkstra(i);
        for(int j=1;j<=n;j++) 
        {
            if(d[j]==INF) sum+=(long long )INF*j;
            else sum+=(long long)j*(d[j]-h[i]+h[j]);
        }
        cout<<sum<<endl;
    }
    return 0;
}

欧拉路

时间复杂度 $O(m\log{m})$

前置知识

欧拉路径：图中所有边恰好经过一次的路径叫欧拉路径（一笔画）欧拉回路：起点与终点相同的欧拉路径叫欧拉回路（可以一直画的一笔画）

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

算法流程

1.判断是否有解记录起点终点 2.记忆当前边跑Dfs

注意

1.建边细节 2.cmp细节 3.当前弧优化（雾

code

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

const int N = (int)1e5+5;
const int M = (int)2e5+5;

int edgeid,head[N];
struct edge{int v,nxt;}e[M];
void addedge(int u,int v){edgeid++;e[edgeid].v=v;e[edgeid].nxt=head[u];head[u]=edgeid;}
bool vis[M];
stack<int> stk;

struct Bian{int u,v;}bian[M];

int rin[N],rout[N],n,m,st,ed,cur[N];

void Dfs(int u)
{
    for(int i=cur[u];i;i=cur[u]) 
    {
        cur[u]=e[i].nxt;
        Dfs(e[i].v);
    }
    stk.push(u);
}

bool cmp(Bian x,Bian y) {return (x.u!=y.u) ? x.u<y.u : x.v>y.v;}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++) 
    {
        int u,v;
        cin>>u>>v;
        bian[i].u=u;
        bian[i].v=v;
        rin[v]++;
        rout[u]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(rin[i]==rout[i]+1) 
        {
            if(ed) return !(cout<<"No");
            else ed=i;
        }
        if(rout[i]==rin[i]+1)
        {
            if(st) return !(cout<<"No");
            else st=i;
        }
    }
    if(!st) st=1;
    sort(bian+1,bian+1+m,cmp);
    for(int i=1;i<=m;i++)
    {
        addedge(bian[i].u,bian[i].v);
    }
    for(int i=1;i<=n;i++) cur[i]=head[i];
    Dfs(st);
    while(!stk.empty()) cout<<stk.top()<<" ",stk.pop();
    return 0;
}

二分图

前置芝士

一般地：

$|最大匹配|=|最小点覆盖|$ (二分图) $|最小边覆盖|+|最大匹配|=|点集|$ （无孤立点的图） $最大独立集+最小点覆盖=点集$ （任意图）

在二分图中：

$|最大匹配|=|最小点覆盖|=a$ $|最小边覆盖|=|最大独立集|=b$ $a+b=|点集|$

二分图判定

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

匈牙利算法

时间复杂度 $O(nm)$

算法流程

1.以下是跑Ntr算法要用的一些东西如果题里没直接给，应该想办法先搞出来

左边的点（和右边的点）左边的点指向右边的点的边 vis数组用于记录每次增广中一个右边的点是否已经被访问（如果已经访问过就没必要再访问了） match数组用于记录每一个右边点现在匹配的左边点

2.递归调用，过于显然

code

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

const int N= 505;
const int M= (int)5e4;

int n,m,c;

int g[505][505];

int match[N];
bool vis[N];

int ans;

bool Ntr(int u)
{
    for(int i=1;i<=m;i++)
    {
        if(g[u][i]==1 && !vis[i])
        {
            vis[i]=1;
            if(!match[i] || Ntr(match[i])) 
            {   
                match[i]=u;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    cin>>n>>m>>c;
    for(int i=1;i<=c;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        g[u][v]=1;
    }
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        if(Ntr(i)) ans++;
    }
    cout<<ans;
    return 0;
}

DAG最小链覆盖

DAG最小不可重链覆盖

DAG最小不可重链覆盖的解法如下：把所有结点i拆为结点i和结点′i ，如果图G中存在有向边i⇒j，则在二分图中引入边i⇒′j 。设二分图的最大匹配数为m，则结果就是n−m。为什么呢？因为匹配和链覆盖是一一对应的。对于链覆盖中的每条链，除了最后一个“结尾结点”之外都有唯一的后继与它对应（即匹配结点），因此匹配数就是非结尾结点的个数。当匹配数达到最大时，非结尾结点的个数也将达到最大。此时，结尾结点的个数最少，即链条数最少

DAG最小可重链覆盖

我们一般先用Floyd求原图的传递闭包，接着求这个闭包偏序集的最小不可重链覆盖 ~~正确性很显然~~

网络流

Dinic

时间复杂度 $O(n^2m)$

算法流程

1.递归调用，都很显然

code

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

#define ll long long 

const int N = 205;
const int M = 5005;

int n,m;
int st,ed;

int edgeid=1;
int head[N];
struct edge
{
    int v,nxt;
    ll w;
}e[M*2];
void addedge(int u,int v,ll w)
{
    edgeid++;
    e[edgeid].v=v;
    e[edgeid].w=w;
    e[edgeid].nxt=head[u];
    head[u]=edgeid;
    edgeid++;
    e[edgeid].v=u;
    e[edgeid].w=0;
    e[edgeid].nxt=head[v];
    head[v]=edgeid;
}

int dep[N];
int cur[N];
queue<int> q;
bool Bfs()
{
    while(!q.empty()) q.pop();
    q.push(st);
    for(int i=1;i<=n;i++) cur[i]=head[i],dep[i]=0;
    dep[st]=1;
    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 && !dep[v])
            {
                dep[v]=dep[u]+1;
                if(v==ed) return 1;
                q.push(v);
            }
        }
    }
    return 0;
}

ll Dfs(int u,ll rst)
{
    if(u==ed || !rst) return rst;
    ll sum=0;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        cur[u]=i;
        ll f;
        if(dep[v]==dep[u]+1 && (f=Dfs(v,min(rst,e[i].w))) )
        {
            sum+=f;
            rst-=f;
            e[i].w-=f;
            e[i^1].w+=f;
            if(!rst) break;
        }
    }
    if(!sum) dep[u]=0;
    return sum;
}

int main()
{
    cin>>n>>m>>st>>ed;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        ll w;
        scanf("%d%d%lld",&u,&v,&w);
        addedge(u,v,w);
    }
    ll ans=0;
    while(Bfs())
    {
        ans+=Dfs(st,LLONG_MAX);
    }
    cout<<ans;
    return 0;
}

网络流求二分图最大匹配

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

const int N = 505*2;
const int M = (int) 5e4+114514;
const int INF = 0x3f3f3f3f;

queue<int> q;
int cur[N],head[N],dep[N],n,m,c,st,ed,edgeid=1,ans;
struct edge{int v,nxt,w;}e[M*2];
void addedge(int u,int v,int w)     
{
    edgeid++;
    e[edgeid].v=v;
    e[edgeid].w=w;
    e[edgeid].nxt=head[u];
    head[u]=edgeid;

    edgeid++;
    e[edgeid].v=u;
    e[edgeid].w=0;
    e[edgeid].nxt=head[v];
    head[v]=edgeid;
}

bool Bfs()
{
    for(int i=st;i<=ed;i++) cur[i]=head[i],dep[i]=0;
    while(!q.empty()) q.pop();
    q.push(st);
    dep[st]=1;
    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 && !dep[v])
            {
                dep[v]=dep[u]+1;
                if(v==ed) return 1;
                q.push(v);
            }
        }
    }
    return 0;
}

int Dfs(int u,int rst)
{
    if(!rst || u==ed) return rst;
    int sum=0;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        cur[u]=i;
        int v=e[i].v;
        int f;
        if(dep[v]==dep[u]+1 && (f=Dfs(v,min(rst,e[i].w))))
        {
            rst-=f;
            sum+=f;
            e[i].w-=f;
            e[i^1].w+=f;
            if(!rst) break;
        }
    }
    if(!sum) dep[u]=-1;
    return sum;
}

void Dinic() {while(Bfs()) ans+=Dfs(st,INF);}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>c;
    st=0;
    ed=n+m+1;
    for(int i=1;i<=n;i++) addedge(st,i,1);
    for(int i=n+1;i<=n+m;i++) addedge(i,ed,1);
    for(int i=1;i<=c;i++)
    {
        int u,v;
        cin>>u>>v;
        addedge(u,v+n,1);
    }
    Dinic();
    cout<<ans;
    return 0;
}

Dinic优化

时间复杂度

随机图： $O(km)(k约为10)$ 上界： $O(nmlogc_{max})(实际上构造出O(nm)的数据都是极难的)$

优化流程

1.离线，对边按权从大到小排序 2.二进制位数相同的边称为一组，按位数从大到小，对每个不同的二进制位位数执行3 3.加入这组边，跑Dinic(不加反向边) 4.加入所有反向边，跑Dinic

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

#define ll long long 

const int N = 1205;
const int M = 120005;

int n,m;
int st,ed;
ll ans;
bool rev;

int edgeid=1;
int head[N];
struct edge
{
    int v,nxt;
    ll w;
}e[M*2];
void addedge(int u,int v,ll w)
{
    edgeid++;
    e[edgeid].v=v;
    e[edgeid].w=w;
    e[edgeid].nxt=head[u];
    head[u]=edgeid;
    edgeid++;
    e[edgeid].v=u;
    e[edgeid].w=0;
    e[edgeid].nxt=head[v];
    head[v]=edgeid;
}

struct bian {int u,v;ll w;} b[M*2];
bool cmp(bian x,bian y) {return x.w>y.w;}

int dep[N];
int cur[N];
queue<int> q;
bool Bfs()
{
    while(!q.empty()) q.pop();
    q.push(st);
    for(int i=1;i<=n;i++) cur[i]=head[i],dep[i]=0;
    dep[st]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            if(i&1&rev) continue;
            int v=e[i].v;
            if(e[i].w && !dep[v])
            {
                dep[v]=dep[u]+1;
                if(v==ed) return 1;
                q.push(v);
            }
        }
    }
    return 0;
}

ll Dfs(int u,ll rst)
{
    if(u==ed || !rst) return rst;
    ll sum=0;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        if(i&1&rev) continue;
        int v=e[i].v;
        cur[u]=i;
        ll f;
        if(dep[v]==dep[u]+1 && (f=Dfs(v,min(rst,e[i].w))) )
        {
            sum+=f;
            rst-=f;
            e[i].w-=f;
            e[i^1].w+=f;
            if(!rst) break;
        }
    }
    if(!sum) dep[u]=0;
    return sum;
}

void Dinic(){while(Bfs()) ans+=Dfs(st,LLONG_MAX);}

int main()
{
    // freopen("working.in","r",stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>st>>ed;
    for(int i=1;i<=m;i++) cin>>b[i].u>>b[i].v>>b[i].w;
    sort(b+1,b+m+1,cmp);
    rev=1;
    for(int k=32,i=0;k>=1 && i<=m;k--)
    {
        while(b[i+1].w>=(1<<(k-1)) && i<m) 
        {
            i++;
            addedge(b[i].u,b[i].v,b[i].w);
        }
        Dinic();
    }
    rev=0;
    Dinic();
    cout<<ans;
    return 0;
}

预流推进

此节过长，故单独移出

【题解】P4722 【模板】最大流加强版 / 预流推进

最小割

显然，最小割=最大割

建议找一张图来感受一下 “不要试图理解它，而是感受它” 没什么卵用还看不懂一点的证明(OI wiki)

二选一模型

例题引入: 有 $N$ 个任务，每个任务可以在机器 A 或机器 B 上完成，花费分别为 $a_i$ 或 $b_i$ 。有 $M$ 对关系，每对关系为二元组 $(x,y)$ ，表示第 $i$ 个任务和第 $j$ 个任务如果在不同的机器上完成，则增加 $v$ 的花费。问如何安排完成每个任务的机器，使总花费最小。

构造

1.转化为最小割，跟起点在一起记为机器A，跟终点在一起记为机器B 2.st向每个点连边，如果割掉即为机器B，所以这条边权值为 $b_i$ 同理，每个点向ed连边，如果割掉即为机器A，所以这条边边权为 $a_i$ 3.对于每个二元组 $(x,y)$ ,在 $x$ , $y$ 之间连双向边，如果割掉任意一条即为不在同一个机器，所以这条边边权为 $v$ 4.跑最大流，即为最小花费

最大权闭合子图

前置芝士

闭合子图：闭合子图是这样一个点集 $V'$ ,满足 $V'$ 是 $V$ 的子集且对于任意的 $u∈V'$ 的任意出边 $(u,v)∈E$ 必然有 $v∈V'$ 成立最大权闭合子图：给每个点赋一个点权，最大权闭合子图就是一个点权之和最大的闭合子图

构造

1.首先假设所有正权点都选，所有负权点都不选，答案初始值为正点权之和 2.转化为求最小割，跟起点在同一个集合里的点为记为选，跟终点在一个集合里的点记为不选 3.若w[i]>0 连边st->i权值为w[i] 意义为如果不选i(割掉这条边)代价为w[i] 若w[i]<0 连边i->ed权值为-w[i] 意义为如果选了i(割掉这条边)代价为-w[i] 4.求最小割(最大流)的结果即为最小代价，答案减去这个代价即为最大闭合权子图的最大权，最后一次Bfs能访问到的点即为跟起点在一起的点集

最小割集

性质

关于最小割的可行边，以下命题等价

1.一条边 $x,y$ 可以在最小割中 2. $x,y$ 的容量减少后最大流（最小割）也减小了 3.跑完最大流的残量网络中，不存在 $x->y$ 的路径 4. $x,y$ 满流，且 $x,y$ 在跑完最大流的残量网络上不属于同一个SCC

关于最小割的必须边，以下命题等价

1.一条边 $x,y$ 必须在最小割中 2. $x,y$ 的容量增大后最大流（最小割）也增大了 3.跑完最大流的残量网络中，存在 $S->x,y->T$ 的路径 4.跑完最大流的残量网络中， $S,x$ 同属一个SCC， $y,T$ 同属一个SCC

算法分析

假设源点为 $S$ ，汇点为 $T$ ，最小割将点集分为两个点集 $S$ 、 $T$ 。首先，点集 $S$ 、 $T$ 不一定是唯一的。点集 $S$ 的一种情况:在残留网络中从源点出发，能走到的所有点都属于 $S'$ 。点集 $T$ 的一种情况:在残留网络的反图(原图的边 $(u,v)$ 在反图中就变成 $(v,u)$ )中从汇点出发，能走到的所有点都属于 $T'$ 。显然，如果一个点既不属于 $S'$ 也不属于 $T'$ ，这个点可以属于 $S$ 也可以属于 $T$ ，最小割是不唯一的又很显然，如果没有任意一个点既不属于 $S'$ 也不属于 $T'$ ，那么最小割唯一

费用流

Zkw

时间复杂度 $O(反正很快)$

注意

1.细节很多

code

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

#define ll long long
const int N= (int)5e3+3;
const int M =(int)5e4+4;
const ll INF = (0x3f3f3f3f3f3f3f3f);

int n,m,st,ed;
ll maxflow,ans;

bool vis[N],inq[N];
ll dis[N];

int edgeid=1;
int head[N];
struct edge
{
    int v,nxt;
    ll cost,w;
}e[M*2];
void addedge(int u,int v,ll w,ll cost)
{
    edgeid++;
    e[edgeid].v=v;
    e[edgeid].w=w;
    e[edgeid].cost=cost;
    e[edgeid].nxt=head[u];
    head[u]=edgeid;

    edgeid++;
    e[edgeid].v=u;
    e[edgeid].w=0;
    e[edgeid].cost=-cost;
    e[edgeid].nxt=head[v];
    head[v]=edgeid;
}

deque<int> q;
bool Spfa()
{
    for(int i=1;i<=n;i++) dis[i]=0x3f3f3f3f3f3f3f3f;
    q.push_front(ed);
    dis[ed]=0;
    inq[ed]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop_front();
        inq[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(dis[v]>dis[u]-e[i].cost && e[i^1].w)
            {
                dis[v]=dis[u]-e[i].cost;
                if(!inq[v])
                {
                    if(!q.empty() && dis[v]<dis[q.front()]) q.push_front(v);
                    else q.push_back(v);
                    inq[v]=1;
                }
            }
        }
    }
    return (dis[st]<0x3f3f3f3f3f3f3f3f);
}

ll Dfs(int u,ll rst)
{
    vis[u]=1;
    if(u==ed || !rst) return rst;
    ll sum=0;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        ll f;
        if(dis[v]==dis[u]-e[i].cost && e[i].w && !vis[v]  
        &&(f=Dfs(v,min(rst,e[i].w))))
        {
            sum+=f;
            rst-=f;
            e[i].w-=f;
            e[i^1].w+=f;
            if(!rst) break;
        }
    }
    return sum;
}

void Zkw()
{
    while(Spfa())
    {
        do
        {
            for(int i=1;i<=n;i++) vis[i]=0;
            ll tmp=Dfs(st,INF);
            maxflow+=tmp;
            ans+=tmp*dis[st];
        }while(vis[ed]);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>st>>ed;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        ll cost,w;
        cin>>u>>v>>w>>cost;
        addedge(u,v,w,cost);
    }
    Zkw();
    cout<<maxflow<<" "<<ans;
    return 0;
}

原始对偶

(待填)

SCC

懒得写了

code

//强连通分量
//lg 2863 求强连通分量的数量
#include<bits/stdc++.h>
using namespace std;

const int N = (int)2e4+4;

int where[N];//这个点在哪个scc里
int scccnt;
int sccsize[N];
int low[N],dfn[N],idx;
bool instk[N];
stack<int> stk;

vector<int> e[N];
int n,m;

void Tarjan(int u)
{
    dfn[u]=low[u]=++idx;
    instk[u]=true;
    stk.push(u);
    for(int v : e[u])
    {
        if(!dfn[v])
        {
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instk[v])
        {
            low[u]=min(low[u],dfn[v]);
            //low[u]=min(low[u],low[v]);
        }
    }
    if(dfn[u]==low[u])
    {
        scccnt++;
        while(stk.top()!=u)
        {
            instk[stk.top()]=false;
            where[stk.top()]=scccnt;
            sccsize[scccnt]++;
            stk.pop();
        }
        sccsize[scccnt]++;
        where[u]=scccnt;
        instk[u]=false;
        stk.pop();
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        e[u].push_back(v);
    }
    for(int i=1;i<=n;i++) Tarjan(i);
    int cnt=0;
    for(int i=1;i<=scccnt;i++) if(sccsize[i]>1) cnt++;
    cout<<cnt;
    return 0;
}

关于图论的一切

存图

邻接表

邻接矩阵

边集

最小生成树

Kruskal

时间复杂度O(mlog⁡m)O(m\log{m})O(mlogm)

算法流程

注意

code

Prim

时间复杂度O(mlog⁡m)O(m\log{m})O(mlogm)

算法流程

注意

code

最短路

Dijkstra

时间复杂度O(mlog⁡m)O(m\log{m})O(mlogm)

算法流程

code

Spfa

时间复杂度O(km)O(km)O(km) (死了)

算法流程

code

Floyd

时间复杂度O(n3)O(n^3)O(n3)

算法流程

code

Johnson

时间复杂度O(nmlog⁡m)O(nm\log{m})O(nmlogm)

算法流程（极简版）

code

欧拉路

时间复杂度 O(mlog⁡m)O(m\log{m})O(mlogm)

前置知识

算法流程

注意

code

二分图

前置芝士

一般地：

在二分图中：

二分图判定

匈牙利算法

时间复杂度O(nm)O(nm)O(nm)

算法流程

code

DAG最小链覆盖

DAG最小不可重链覆盖

DAG最小可重链覆盖

网络流

Dinic

时间复杂度O(n2m)O(n^2m)O(n2m)

算法流程

code

网络流求二分图最大匹配

Dinic优化

时间复杂度

优化流程

预流推进

【题解】P4722 【模板】最大流 加强版 / 预流推进

最小割

二选一模型

构造

最大权闭合子图

前置芝士

构造

最小割集

性质

关于最小割的可行边，以下命题等价

关于最小割的必须边，以下命题等价

算法分析

费用流

Zkw

时间复杂度O(反正很快)O(反正很快)O(反正很快)

注意

code

原始对偶

SCC

时间复杂度 $O(m\log{m})$

时间复杂度 $O(m\log{m})$

时间复杂度 $O(m\log{m})$

时间复杂度 $O(km)$ (死了)

时间复杂度 $O(n^3)$

时间复杂度 $O(nm\log{m})$

时间复杂度 $O(m\log{m})$

时间复杂度 $O(nm)$

时间复杂度 $O(n^2m)$

【题解】P4722 【模板】最大流加强版 / 预流推进

时间复杂度 $O(反正很快)$