OI模板-图论
最短路算法
dijkstra
优先队列优化 \(O((n+m)\log m)\)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)
#define M (int)(2e5+15)
int n,m,pos=1,d[N],vis[N],head[N];
struct Edge{int u,v,w,next;} e[M];
struct node{int u,dis;};
bool operator<(node a,node b){return a.dis>b.dis;}
priority_queue<node> q;
void addEdge(int u,int v,int w)
{
e[++pos]={u,v,w,head[u]};
head[u]=pos;
}
void dijkstra(int st)
{
for(int i=1; i<=n; i++) vis[i]=0,d[i]=INF;
d[st]=0; q.push({st,0});
while(!q.empty())
{
int u=q.top().u; q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].v,w=e[i].w;
if(d[v]>d[u]+w)
{
d[v]=d[u]+w;
q.push({v,d[v]});
}
}
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int st; cin >> n >> m >> st;
for(int i=1,u,v,w; i<=m; i++)
{
cin >> u >> v >> w;
addEdge(u,v,w);
}
dijkstra(st);
for(int i=1; i<=n; i++)
cout << (d[i]==INF?-1:d[i]) << " \n"[i==n];
return 0;
}SPFA
时间复杂度 \(O(nm)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e3+15)
int n,m;
int d[N],vis[N];
struct Edge
{
int u,v,w,next;
}e[N];
int pos=1,head[N];
void addEdge(int u,int v,int w)
{
e[++pos]={u,v,w,head[u]};
head[u]=pos;
}
queue<int> q;
void spfa()
{
memset(d,0x3f,(n+1)*sizeof(int));
memset(vis,0,(n+1)*sizeof(int));
d[1]=0;vis[1]=1;
q.push(1);
while(!q.empty())
{
int u=q.front();q.pop();
vis[u]=0;
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].v;
if(d[v]>d[u]+e[i].w)
{
d[v]=d[u]+e[i].w;
if(!vis[v])
q.push(v),vis[v]=1;
}
}
}
}
signed main()
{
ios::sync_with_stdio(0);
cin >> n >> m;
for(int i=1,u,v,w; i<=m; i++)
{
cin >> u >> v >> w;
addEdge(u,v,w);
}
spfa();
for(int i=1; i<=n; i++)
cout << (d[i]==INF?-1:d[i]) << " \n"[i==n];
return 0;
}分层图最短路
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e4+5)
#define M (int)(5e4+5)
#define K (int)(11)
struct Edge
{
int u,v,w,next;
}e[M*(K+1)*4];
int n,m,k,s,t,pos=1,head[N*(K+1)],d[N*(K+1)],vis[N*(K+1)];
struct node{int u,dis;};
bool operator<(node a,node b){return a.dis>b.dis;}
priority_queue<node> q;
void addEdge(int u,int v,int w)
{
e[++pos]={u,v,w,head[u]};
head[u]=pos;
}
void dijkstra(int st)
{
memset(d,0x3f,sizeof(d));
q.push({st,0}); d[st]=0;
while(!q.empty())
{
int u=q.top().u; q.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].v,w=e[i].w;
if(d[v]>d[u]+w)
{
d[v]=d[u]+w;
q.push({v,d[v]});
}
}
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> m >> k >> s >> t; ++s; ++t;
for(int i=1,u,v,w; i<=m; i++)
{
cin >> u >> v >> w; ++u; ++v;
addEdge(u,v,w);addEdge(v,u,w);
for(int j=1; j<=k; j++)
{
addEdge(j*n+u,j*n+v,w);
addEdge(j*n+v,j*n+u,w);
addEdge((j-1)*n+u,j*n+v,0);
addEdge((j-1)*n+v,j*n+u,0);
}
}
for(int i=1; i<=k; i++)
addEdge((i-1)*n+t,i*n+t,0);
dijkstra(s);
cout << d[k*n+t] << '\n';
return 0;
}最小生成树
都是无向图！！！！有向图的叫最小树形图！！！
kruskal
时间复杂度 \(O(m\log m)\)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(5e3+15)
#define M (int)(2e5+15)
int n,m,pos,res,head[N],f[N];
struct Edge{int u,v,w;}e[M];
bool operator<(Edge a,Edge b){return a.w<b.w;}
void init(int n){for(int i=1; i<=n; i++) f[i]=i;}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void merge(int u,int v){f[find(u)]=find(v);}
int kruskal()
{
sort(e+1,e+1+m); int res=0,cnt=0;
for(int i=1; i<=m&&cnt<n-1; i++)
if(find(e[i].u)!=find(e[i].v))
{
merge(e[i].u,e[i].v);
res+=e[i].w; ++cnt;
}
return (cnt!=n-1)?-1:res;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> m; init(n);
for(int i=1,u,v,w; i<=m; i++)
{
cin >> u >> v >> w;
e[i]={u,v,w};
}
int ans=kruskal();
if(ans==-1)cout << "orz";
else cout << ans;
return 0;
}Boruvka
时间复杂度 \(O(m\log n)\)
空间复杂度 \(O(m)\)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(5e3+15)
#define M (int)(2e5+15)
int n,m,head[N],f[N],best[M],vis[M];
struct Edge{int u,v,w;}e[M];
void init(int n){for(int i=1; i<=n; i++) f[i]=i;}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void merge(int u,int v){f[find(u)]=find(v);}
bool cmp(int a,int b)
{
if(!b) return 1;
if(e[a].w==e[b].w) return a<b;
return e[a].w<e[b].w;
}
int boruvka()
{
int res=0,cnt=0,ok=1;
while(ok)
{
for(int i=0; i<=m; i++) best[i]=0;
for(int i=1,u,v; i<=m; i++)
{
if(vis[i]) continue;
u=find(e[i].u),v=find(e[i].v);
if(u==v) continue;
if(cmp(i,best[u])) best[u]=i;
if(cmp(i,best[v])) best[v]=i;
}
ok=0;
for(int i=1; i<=n&&cnt<n-1; i++)
if(best[i]&&!vis[best[i]])
{
vis[best[i]]=1; ++cnt; ok=1;
res+=e[best[i]].w;
merge(e[best[i]].u,e[best[i]].v);
}
}
return (cnt!=n-1)?-1:res;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> m; init(n);
for(int i=1,u,v,w; i<=m; i++)
{
cin >> u >> v >> w;
e[i]={u,v,w};
}
int ans=boruvka();
if(ans==-1) cout << "orz";
else cout << ans << '\n';
return 0;
}Prim
优先队列优化的时间复杂度 \(O(m\log n)\)
斐波那契堆优化的时间复杂度 \(O(n\log n)\)
下面的代码是无优化邻接矩阵版的，\(O(n^2)\) ，仅适用于稠密图 \(n\le 2000\) ，不然会挂（MLE或TLE）
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e3+15)
int n,m;
int ans,d[N],vis[N],g[N][N];
void prim()
{
memset(d,0x3f,(n+1)*sizeof(int));
for(int i=1; i<n; i++)
{
int u=0;
for(int j=1; j<=n; j++)
if(!vis[j]&&(!u||d[j]<d[u])) u=j;
vis[u]=1;
for(int j=1; j<=n; j++)
if(!vis[j])d[j]=min(d[j],g[u][j]);
}
for(int i=2; i<=n; i++)
ans+=d[i];
}
signed 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++)
if(i!=j)g[i][j]=INF;
for(int i=1,u,v,w; i<=m; i++)
{
cin >> u >> v >> w;
g[v][u]=g[u][v]=min(g[u][v],w);
}
prim();
cout << ans << endl;
return 0;
}LCT
比较离谱的解法之一
大常数
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() getchar()
#define pc(a) putchar(a)
#define N (int)(4e5+5)
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
if(k>9)write(k/10);
pc(k%10+'0');
}
int n,m,idx,ans,cnt;
namespace LCT
{
struct node
{
int ch[2],w,id,fa,sz,mx,tag;
}t[N];
#define isroot(x) ((t[t[x].fa].ch[0]!=x)&&(t[t[x].fa].ch[1]!=x))
void pushr(int x)
{
swap(t[x].ch[0],t[x].ch[1]);
t[x].tag^=1;
}
void push_up(int x)
{
t[x].id=x;t[x].mx=t[x].w;
if(t[t[x].ch[0]].mx>t[x].mx)
t[x].mx=t[t[x].ch[0]].mx,t[x].id=t[t[x].ch[0]].id;
if(t[t[x].ch[1]].mx>t[x].mx)
t[x].mx=t[t[x].ch[1]].mx,t[x].id=t[t[x].ch[1]].id;
}
void push_down(int x)
{
if(t[x].tag)
{
if(t[x].ch[0])pushr(t[x].ch[0]);
if(t[x].ch[1])pushr(t[x].ch[1]);
t[x].tag=0;
}
}
void push_all(int x)
{
if(!isroot(x))push_all(t[x].fa);
push_down(x);
}
void rotate(int x)
{
int y=t[x].fa;
int z=t[y].fa;
int k=t[y].ch[1]==x;
if(!isroot(y))t[z].ch[t[z].ch[1]==y]=x;
t[x].fa=z;
t[y].ch[k]=t[x].ch[k^1];
t[t[x].ch[k^1]].fa=y;
t[x].ch[k^1]=y;
t[y].fa=x;
push_up(y);
push_up(x);
}
void splay(int x)
{
push_all(x);
while(!isroot(x))
{
int y=t[x].fa;
int z=t[y].fa;
if(!isroot(y))
(t[z].ch[1]==y)^(t[y].ch[1]==x)?rotate(x):rotate(y);
rotate(x);
}
}
void access(int x)
{
for(int y=0; x; y=x,x=t[x].fa)
splay(x),t[x].ch[1]=y,push_up(x);
}
void make_root(int x)
{
access(x);splay(x);
pushr(x);
}
int find_root(int x)
{
access(x);splay(x);
while(t[x].ch[0])push_down(x),x=t[x].ch[0];
splay(x);
return x;
}
void split(int x,int y)
{
make_root(x);
access(y);splay(y);
}
void link(int x,int y)
{
make_root(x);
if(find_root(y)!=x)t[x].fa=y;
}
int ck(int x,int y)
{
make_root(x);
return find_root(y)!=x;
}
void cut(int x,int y)
{
make_root(x);
if(find_root(y)==x&&t[y].fa==x&&!t[y].ch[0])
{
t[x].ch[1]=t[y].fa=0;
push_up(x);
}
}
}
signed main()
{
using namespace LCT;
read(n);read(m);
idx=n;
for(int i=1,x,y,z; i<=m; i++)
{
read(x);read(y);read(z);
t[++idx].w=z;
if(x!=y&&ck(x,y))link(x,idx),link(idx,y),ans+=z,++cnt;
else
{
split(x,y);int now=t[y].id;
if(t[now].mx<=z)continue;
ans-=t[now].mx-z;splay(now);
t[t[now].ch[0]].fa=t[t[now].ch[1]].fa=0;
link(x,idx);link(idx,y);
}
}
if(cnt<n-1)puts("orz");
else write(ans),pc('\n');
return 0;
}线段树优化建图
板子1
\(n\) 个结点， \(q\) 次操作，问操作后从 \(s\) 出发的单源最短路
操作如下
- 输入
1 u v w表示 \(u\) 到 \(v\) 连一条有向边 - 输入
2 u l r w表示 \(u\) 到 \([l,r]\) 的每个结点连一条有向边 - 输入
3 u l r w表示 \([l,r]\) 的每个结点向 \(u\) 连一条有向边
对于 \(100\%\) 的数据，\(1\le n,q \le 10^5\)，\(1\le w \le 10^9\)
代码：
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
#include <bitset>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define DEBUG puts("-------------")
namespace FastIO
{
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e6+15)
char buf1[SIZ],*p1,*p2;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
}using namespace FastIO;
#define N ((int)(1e5+15))
const int D=5e5+15; // 两棵线段树的分界点
int n,m,s,d[N*10+255],a[N*10+255]; // a是结点编号对应的线段树叶子结点的编号
bitset<N*10+255> vis;
struct node1{int v,w;}; // 边
struct show_l_r{int l,r;}tr[N<<2]; // 辅助树
vector<node1> g[N*10+255]; // 两棵线段树
struct node2{int u,dis;};
bool operator<(node2 a,node2 b){return a.dis>b.dis;}
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
void build(int l,int r,int at)
{
tr[at].l=l; tr[at].r=r;
if(l==r) return a[l]=at, void(0);
int mid=(l+r)>>1;
g[at].push_back({ls(at),0});
g[at].push_back({rs(at),0});
g[ls(at)+D].push_back({at+D,0});
g[rs(at)+D].push_back({at+D,0});
build(l,mid,ls(at)); build(mid+1,r,rs(at));
}
void link(int nl,int nr,int u,int w,int opt,int at)
{
int l=tr[at].l,r=tr[at].r;
if(nl<=l&&r<=nr)
{
if(opt) g[at+D].push_back({u,w});
else g[u+D].push_back({at,w});
return;
}
int mid=(l+r)>>1;
if(nl<=mid) link(nl,nr,u,w,opt,ls(at));
if(nr>mid) link(nl,nr,u,w,opt,rs(at));
}
void Dijkstra(int st)
{
priority_queue<node2> q;
memset(d,0x3f,sizeof(d));
d[st]=0; vis=0; q.push({st,0});
while(!q.empty())
{
int u=q.top().u; q.pop();
if(vis[u]) continue;
vis[u]=1;
for(auto i : g[u])
{
int v=i.v,w=i.w;
if(d[v]>d[u]+w)
{
d[v]=d[u]+w;
q.push({v,d[v]});
}
}
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
read(n); read(m); read(s);
build(1,n,1);
for(int i=1,op,u,v,l,r,w; i<=m; i++)
{
read(op);
if(op==1)
{
read(u); read(v); read(w);
g[a[u]].push_back({a[v],w});
}
else
{
read(u); read(l); read(r); read(w);
link(l,r,a[u],w,op&1,1); // op=2: u->[l,r] , op=3:[l,r]->u;
}
}
for(int i=1; i<=n; i++)
{
g[a[i]].push_back({a[i]+D,0}),
g[a[i]+D].push_back({a[i],0});
}
Dijkstra(a[s]+D);
for(int i=1; i<=n; i++)
write(d[a[i]]!=INF ? d[a[i]] : -1),pc(" \n"[i==n]);
return 0;
}板子2
咕咕咕。。。
判负环
板子题 P3385 【模板】负环 ，这题是判断从结点 \(1\) 为起点的负环
SPFA
// 2023年03月11日 01:05:55
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e3 + 15))
vector< pair<int,int> > vec[N];
int n,m,cnt[N],d[N]; char vis[N];
#define addEdge(u,v,w) vec[u].emplace_back(v,w)
void clear() { for(int i = 1; i <= n; i++) vec[i].clear(); }
bool spfa(int s) // 从 s 开始的负环
{
memset(vis, 0, (n + 5) * sizeof(char));
memset(cnt, 0, (n + 5) * sizeof(int));
memset(d, 0x3f, (n + 5) * sizeof(int));
queue<int> q; q.push(s); vis[s] = 1; d[s] = 0;
for(int v,w; !q.empty(); )
{
int u = q.front(); q.pop(); vis[u] = 0;
for(pii it : vec[u])
{
v = it.first, w = it.second;
if(d[v] > d[u] + w)
{
d[v] = d[u] + w;
if(!vis[v])
{
//++cnt[v]; // 判法1：入队次数
cnt[v] = cnt[u] + 1; // 判法2：最短路长度
if(cnt[v] == n) return 1; // 在涉及虚点的题中可能会改成 n+1
q.push(v); vis[v] = 1;
}
}
}
}
return 0;
}
void solve()
{
cin >> n >> m; clear();
for(int i = 1, u, v, w; i <= m; i++)
{
cin >> u >> v >> w;
addEdge(u,v,w); if(!(w < 0)) addEdge(v,u,w);
}
cout << (spfa(1) ? "YES" : "NO") << '\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int Q; cin >> Q; while(Q--) solve();
return 0;
}Bellman-Ford
不适用于判断 \(u\) 结点出发的负环，但是适合全局负环
故洛谷板子题会 WA11 ，因为板子题是求的1出发能到的负环。
但是求图是否有负环是正确的。
时间复杂度 \(O(nm)\) ，常数极小。
代码：
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
#include <bitset>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(2e3+15))
#define M ((int)(1e4+15))
int n,m,pos=1,head[N],d[N];
struct Edge{int u,v,w,next;} e[M];
void addEdge(int u,int v,int w)
{
e[++pos]={u,v,w,head[u]};
head[u]=pos;
}
bool work()
{
for(int i=1; i<=n; i++) d[i]=0;
for(int k=1; k<n; k++)
for(int i=2; i<=pos; i++)
{
int u=e[i].u,v=e[i].v,w=e[i].w;
if(d[v] > d[u] + w) d[v]=d[u]+w;
}
for(int i=2; i<=pos; i++)
{
int u=e[i].u,v=e[i].v,w=e[i].w;
if(d[v] > d[u] + w) return 1;
}
return 0;
}
void clear(){pos=1; for(int i=1; i<=n; i++) head[i]=0;}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int Q; cin >> Q;
while(Q--)
{
clear(); cin >> n >> m;
for(int i=1,u,v,w; i<=m; i++)
{
cin >> u >> v >> w;
addEdge(u,v,w);
if(w>=0) addEdge(v,u,w);
}
cout << (work()? "YES\n" : "NO\n");
}
return 0;
}kosaraju算法
时间复杂度 \(O(n+m)\)
空间复杂度 \(O(m)\)
例题：P3387 【模板】缩点
有向图强连通分量缩点
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)
bool vis[N];
vector<int> g1[N],g2[N],vec[N];
int n,m,cnt,scnt,f[N],sum[N],in[N],val[N],scc[N],dfn[N];
void addEdge1(int u,int v)
{
g1[u].push_back(v);
g2[v].push_back(u);
}
void addEdge2(int u,int v)
{
vec[u].push_back(v);
}
void dfs1(int u)
{
vis[u]=1;
for(int v : g1[u])
if(!vis[v]) dfs1(v);
dfn[++cnt]=u;
}
void dfs2(int u,int id)
{
scc[u]=id; sum[id]+=val[u];
for(int v : g2[u])
if(!scc[v]) dfs2(v,id);
}
void kosaraju()
{
for(int i=1; i<=n; i++)
if(!vis[i]) dfs1(i);
scnt=0;
for(int i=n; i>=1; i--)
if(!scc[dfn[i]])
{
++scnt;
dfs2(dfn[i],scnt);
}
}
int topo()
{
queue<int> q;
for(int i=1; i<=scnt; i++)
if(!in[i]) q.push(i),f[i]=sum[i];
while(!q.empty())
{
int u=q.front(); q.pop();
for(int v:vec[u])
{
f[v]=max(f[v],f[u]+sum[v]);
if(!(--in[v])) q.push(v);
}
}
return *max_element(f+1,f+1+scnt);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> m;
for(int i=1; i<=n; i++)
cin >> val[i];
for(int i=1,u,v; i<=m; i++)
{
cin >> u >> v;
addEdge1(u,v);
}
kosaraju();
for(int i=1,u,v; i<=n; i++)
for(int j : g1[i])
{
u=scc[i],v=scc[j];
if(u!=v) addEdge2(u,v),++in[v];
}
cout << topo() << '\n';
return 0;
}Tarjan算法 [连通性问题]
无向图
割边（桥）
时间复杂度 \(O(n)\)
空间复杂度 \(O(m)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define M (int)(6e5+25)
#define N (int)(5e4+25)
struct Edge
{
int u,v,next;
}e[M];
int n,m,ans;
int pos=2,head[N],dfn[N],low[N],dfncnt,cut[M];
void addEdge(int u,int v)
{
e[pos]={u,v,head[u]};
head[u]=pos++;
}
void tarjan(int u,int in_edge)
{
dfn[u]=low[u]=++dfncnt;
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].v;
if(!dfn[v])
{
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u])
cut[i]=cut[i^1]=1;
}else if(i!=(in_edge^1))
low[u]=min(low[u],dfn[v]);
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i=1,u,v; i<=m; i++)
{
cin >> u >> v;
addEdge(u,v);addEdge(v,u);
}
for(int i=1; i<=n; i++)
if(!dfn[i])tarjan(i,0);
for(int i=2; i<pos; i+=2)
if(cut[i])++ans;
cout << ans << endl;
return 0;
}割点（割顶）
区别于桥，这个不用管fa结点，但是注意rt要有两个子结点都是“割点性质“
时间复杂度 \(O(n)\)
空间复杂度 \(O(m)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N (int)(2e4+15)
#define M (int)(2e5+15)
struct node
{
int u,v,next;
}e[M];
int n,m,ans;
int pos=2,head[N],dfncnt,dfn[N],low[N],cut[N];
void addEdge(int u,int v)
{
e[pos]={u,v,head[u]};
head[u]=pos++;
}
void tarjan(int u,int rt)
{
dfn[u]=low[u]=++dfncnt;
int cnt=0;
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].v;
if(!dfn[v])
{
tarjan(v,rt);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
{
++cnt;
if(u!=rt||cnt>1)
cut[u]=1;
}
}low[u]=min(low[u],dfn[v]);
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i=1,u,v; i<=m; i++)
{
cin >> u >> v;
addEdge(u,v);addEdge(v,u);
}
for(int i=1; i<=n; i++)
if(!dfn[i])tarjan(i,i);
for(int i=1; i<=n; i++)
if(cut[i])++ans;
cout << ans << endl;
for(int i=1; i<=n; i++)
if(cut[i])cout << i << " \n"[!--ans];
return 0;
}还有另一种写法，如下
// 2022年10月16日 21:43:19
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e4+15))
#define M ((int)(2e5+15))
int n,m,res,pos=1,head[N],dfn[N],low[N],cut[N];
struct Edge { int u,v,next; } e[M];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
void Tarjan(int u,int f)
{
static int tim = 0; int C = 0;
dfn[u] = low[u] = ++tim;
for(int i=head[u]; i; i=e[i].next)
{
int v = e[i].v;
if(!dfn[v])
{
++C; Tarjan(v,u); down(low[u], low[v]);
if(f && dfn[u] <= low[v]) cut[u] = 1;
}else if(v != f) down(low[u], dfn[v]);
}
if(!f && C > 1) cut[u] = 1;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> m;
for(int i=1,u,v; i<=m; i++)
{
cin >> u >> v;
addEdge(u,v); addEdge(v,u);
}
for(int i=1; i<=n; i++) if(!dfn[i]) Tarjan(i,0);
for(int i=1; i<=n; i++) if(cut[i]) ++res;
cout << res << '\n';
for(int i=1; i<=n; i++) if(cut[i]) cout << i << " \n"[!(--res)];
return 0;
}边双连通分量
时间复杂度 \(O(n)\)
空间复杂度 \(O(m)\)
upd20220806 有个板子题P8436 【模板】边双连通分量了
例题：P2860 [USACO06JAN]Redundant Paths G
当然你也可以用强连通分量的板子来写，因为边双转一下一定是强连通分量。
例题的代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() getchar()
#define pc(a) putchar(a)
#define N (int)(5e3+15)
#define M (int)(2e4+15)
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
if(k>9)write(k/10);
pc(k%10+'0');
}
struct Edge
{
int u,v,next;
}e[M];
int n,m,ans,ecc[N],top;
int pos=2,head[N],stk[N];
int dfn[N],low[N],dfncnt,ecnt,in[N];
void addEdge(int u,int v)
{
e[pos]={u,v,head[u]};
head[u]=pos++;
}
void tarjan(int u,int in_edge)
{
dfn[u]=low[u]=++dfncnt;
stk[++top]=u;
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].v;
if(!dfn[v])
{
tarjan(v,i);
low[u]=min(low[u],low[v]);
}else if(i!=(in_edge^1))
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
ecc[u]=++ecnt;
while(stk[top]!=u)
ecc[stk[top--]]=ecnt;
--top;
}
}
signed main()
{
read(n);read(m);
for(int i=1,u,v; i<=m; i++)
{
read(u);read(v);
addEdge(u,v);addEdge(v,u);
}
for(int i=1; i<=n; i++)
if(!dfn[i])top=0,tarjan(i,0);
for(int i=2; i<pos; i++)
if(ecc[e[i].u]!=ecc[e[i].v])
++in[ecc[e[i].u]],++in[ecc[e[i].v]];
int ans=0;
for(int i=1; i<=ecnt; i++)
if(in[i]==2)++ans;
// 对于所有双连通分量，其缩点(e-dcc)后
// 连(叶结点数+1)/2（即叶结点数除以2向上取整）条边
// 可以使整个图变成双连通图
write((ans+1)>>1);pc('\n');
return 0;
}点双连通分量
时间复杂度 \(O(n)\)
空间复杂度 \(O(m)\)
注：下面的第二种写法才可通过例题！
因为第一种把割点存在了第一个，和例题的标程不一样，然后例题没写special judge.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() getchar()
#define pc(a) putchar(a)
#define N (int)(5e4+15)
#define M (int)(6e5+15)
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
if(k>9)write(k/10);
pc(k%10+'0');
}
struct Edge
{
int u,v,next;
}e[M];
int n,m,vcnt,cut[N],stk[N],top;
int pos=2,head[N],dfn[N],low[N],dfncnt;
vector<int> vcc[N];
void addEdge(int u,int v)
{
e[pos]={u,v,head[u]};
head[u]=pos++;
}
void tarjan(int u,int rt)
{
dfn[u]=low[u]=++dfncnt;
stk[++top]=u;int cnt=0;
if(u==rt&&!head[u])
{
vcc[++vcnt].push_back(u);
return;
}
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].v;
if(!dfn[v])
{
tarjan(v,rt);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
{
++cnt;
if(u!=rt||cnt>1)cut[u]=1;
// 第一种写法，割点在vcc[vcnt][0]
vcc[++vcnt].push_back(u);
while(stk[top]!=v)
vcc[vcnt].push_back(stk[top--]);
vcc[vcnt].push_back(stk[top--]);
/* 第二种写法
int z;++vcnt;
do {
z=stk[top--];
vcc[vcnt].push_back(z);
} while (z!=v);
vcc[vcnt].push_back(u);
*/
}
}else low[u]=min(low[u],dfn[v]);
}
}
signed main()
{
read(n);read(m);
for(int i=1,u,v; i<=m; i++)
{
read(u);read(v);
if(u==v)continue;
addEdge(u,v);addEdge(v,u);
}
for(int i=1; i<=n; i++)
if(!dfn[i])top=0,tarjan(i,i);
for(int i=1; i<=vcnt; i++)
for(int j=0; j<vcc[i].size(); j++)
write(vcc[i][j]),pc(" \n"[j+1==vcc[i].size()]);
return 0;
}有向图
强连通分量缩点
时间复杂度 \(O(n+m)\)
空间复杂度 \(O(n+m)\)
例题：P3387 【模板】缩点
Tarjan缩点后的点的排列顺序是逆拓扑序
// 2022年09月12日 00:28:14
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e4+15))
#define M ((int)(1e5+15))
int n,m,scnt,tim,stktop,pos=1,head[N],f[N];
int val[N],top[N],sum[N],scc[N],stk[N],ins[N],dfn[N],low[N];
struct Edge{int u,v,next; }e[M];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
void tarjan(int u)
{
dfn[u] = low[u] = ++tim;
stk[++stktop] = u; ins[u] = 1;
for(int i=head[u]; i; i=e[i].next)
{
int v = e[i].v;
if(!dfn[v]) { tarjan(v); down(low[u], low[v]); }
else if(ins[v]) down(low[u], dfn[v]);
}
if(dfn[u] == low[u])
{
top[++scnt] = u;
for(int p=0; p!=u; )
{
p = stk[stktop--]; ins[p]=0;
scc[p] = scnt; // ++sz[scnt];
sum[scnt] += val[p];
}
}
}
int solve()
{
for(int u=scnt; u; u--)
{
if(!f[u]) f[u] = sum[u];
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].v;
up(f[v], f[u] + sum[v]);
}
}
return *max_element(f+1,f+1+scnt);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> m;
for(int i=1; i<=n; i++) cin >> val[i];
for(int i=1,u,v; i<=m; i++) { cin >> u >> v; addEdge(u,v); }
for(int i=1; i<=n; i++) if(!dfn[i]) tarjan(i);
pos=1; for(int i=1; i<=n; i++) head[i] = 0;
for(int i=2; i<=m+1; i++)
{
int u = scc[e[i].u], v = scc[e[i].v];
if(u != v) addEdge(u,v);
}
cout << solve() << '\n';
return 0;
}欧拉路径
求的是字典序最小的欧拉路径
/*
g++ test_20220124.cpp -o test_20220124
./test_20220124
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN (int)(1e5+5)
#define gc() getchar()
#define pc(a) putchar(a)
template<typename T>void read(T &k)
{
char ch=gc(); T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
if(k>9)write(k/10);
pc(k%10+'0');
}
int n,m,cnt,s,t;
struct node
{
int v,id;
bool operator<(node &o)
{return v<o.v;}
};
vector<node> vec[MAXN];
int vis[MAXN<<1],in[MAXN],out[MAXN],top,stk[MAXN<<1],del[MAXN];
// del防极限数据 (1->2) * 1e5 && (2->1) * 1e5
void dfs(int u)
{
for(int i=del[u]; i<vec[u].size(); i=max(i+1,del[u])/*可能被更新了*/)
{
if(!vis[vec[u][i].id])
{
vis[vec[u][i].id]=1;
del[u]=i+1;
dfs(vec[u][i].v);
}
}
stk[++top]=u;
}
signed main()
{
read(n);read(m);
for(int i=1,u,v; i<=m; i++)
{
read(u);read(v);
++out[u];++in[v];
vec[u].push_back({v,i});
}
for(int i=1; i<=n; i++)
{
if(in[i]!=out[i])
{
++cnt;
if(in[i]==out[i]-1)s=i;
if(in[i]==out[i]+1)t=i;
}
}
if(cnt!=0&&cnt!=2)return puts("No"),0;
if(cnt==0)s=t=1;
if(!s||!t)return puts("No"),0;
for(int i=1; i<=n; i++)
sort(vec[i].begin(),vec[i].end());
dfs(s);
while(top>0)
{
write(stk[top]);
pc(" \n"[top==1]);--top;
}
return 0;
}欧拉回路
hierholzer算法？待补
2-SAT
参考 2–SAT 学习笔记
// 2024年08月02日 18:08:11
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define pb push_back
#define N ((int)(2e6 + 15))
bool ins[N];
vector<int> vec[N];
int stktop, scnt, stk[N], low[N], dfn[N], scc[N], top[N];
void Tarjan(int u)
{
static int tim = 0; dfn[u] = low[u] = ++tim;
stk[++stktop] = u; ins[u] = true;
for(int v : vec[u])
{
if(!dfn[v]) { Tarjan(v); down(low[u], low[v]); }
else if(ins[v]) down(low[u], dfn[v]);
}
if(low[u] == dfn[u])
{
top[++scnt] = u;
for(int p = 0; p != u; )
{
p = stk[stktop--];
ins[p] = false; scc[p] = scnt;
}
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int n, m; cin >> n >> m;
while(m--)
{
static int i, j; static bool a, b;
cin >> i >> a >> j >> b;
vec[i + n * a].pb(j + n * (!b));
vec[j + n * b].pb(i + n * (!a));
}
rep(i, 1, n * 2) if(!dfn[i]) Tarjan(i);
rep(i, 1, n) if(scc[i] == scc[i + n]) return cout << "IMPOSSIBLE\n", 0;
cout << "POSSIBLE\n";
rep(i, 1, n) cout << (scc[i] < scc[i + n]) << " \n"[i == n];
return 0;
}网络流算法
有向图网络最大流
这里默认s与t连通，实际上代码里写了判断
Dinic
时间复杂度 \(\mathcal{O}(n^2m)\)
空间复杂度 \(\mathcal{O}(n+m)\)
// 2022年10月28日 16:36:03
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(215))
#define M ((int)(5e3+15))
int n,m,s,t,pos=1,head[N],now[N],dep[N];
struct Edge { int u,v,w,next; } e[M * 2];
void addEdge(int u,int v,int w)
{ e[++pos] = {u,v,w,head[u]}; head[u] = pos; }
queue<int> q;
bool bfs()
{
for(int i=1; i<=n; i++) dep[i] = INF;
q.push(s); dep[s] = 1; now[s] = head[s];
while(!q.empty())
{
int u = q.front(); q.pop();
for(int i=head[u]; i; i=e[i].next)
{
int v = e[i].v;
if(e[i].w > 0 && dep[v] == INF)
{
dep[v] = dep[u] + 1;
now[v] = head[v]; q.push(v);
}
}
}
return dep[t] != INF;
}
int dfs(int u,int in)
{
if(u == t) return in;
int out = 0;
for(int i=now[u]; i; i=e[i].next)
{
if(!in) break; int v = e[i].v; now[u] = i;
if(e[i].w > 0 && dep[v] == dep[u] + 1)
{
int res = dfs(v, min(in, e[i].w));
e[i].w -= res; e[i^1].w += res;
in -= res; out += res;
}
}
if(!out) dep[u] = INF;
return out;
}
int Dinic()
{
int res = 0;
while(bfs()) res += dfs(s, INF);
return res;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> m >> s >> t;
for(int i=1,u,v,w; i<=m; i++)
{
cin >> u >> v >> w;
addEdge(u,v,w); addEdge(v,u,0);
}
cout << Dinic() << '\n';
return 0;
}ISAP
时间复杂度 \(O(n^2m)\)
空间复杂度 \(O(m)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e4+15)
#define M (int)(2e4+15)
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+5)
char buf1[SIZ];
char *p1=buf1,*p2=buf1;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
struct Edge
{
int u,v,w,next;
}e[M];
int n,m,s,t,ans;
int pos=1,head[N],dep[N],now[N],gap[N];
void addEdge(int u,int v,int w)
{
e[++pos]={u,v,w,head[u]};
head[u]=pos;
}
queue<int> q;
bool bfs()
{
memset(dep,0x3f,(n+1)*sizeof(int));
q.push(t);dep[t]=1;gap[1]=1;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].v;
if(e[i^1].w>0&&dep[v]==INF)
{
dep[v]=dep[u]+1;
gap[dep[v]]++;
q.push(v);
}
}
}
return dep[s]!=INF;
}
int dfs(int u,int in)
{
if(u==t)
return in;
int out=0;
for(int i=now[u]; i; i=e[i].next)
{
int v=e[i].v;now[u]=i;
if(e[i].w>0&&dep[u]==dep[v]+1)
{
int res=dfs(v,min(in,e[i].w));
e[i].w-=res;
e[i^1].w+=res;
in-=res;
out+=res;
}
if(!in)return out;
}
if(!--gap[dep[u]])dep[s]=n+1;
gap[++dep[u]]++;
return out;
}
void ISAP()
{
bfs();
while(dep[s]<=n)
{
memcpy(now,head,(n+1)*sizeof(int));
ans+=dfs(s,INF);
}
}
signed main()
{
read(n);read(m);read(s);read(t);
for(int i=1,u,v,w; i<=m; i++)
{
read(u);read(v);read(w);
addEdge(u,v,w);addEdge(v,u,0);
}
ISAP();
write(ans);pc('\n');
return 0;
}HLPP
n=5e3,m=5e4
时间复杂度 \(O(n^2\sqrt{m}\log n)\)
空间复杂度 \(O(m)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
// #define INF 0x3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define N (int)(2e3+15)
#define M (int)(3e5+15)
#define SIZ (int)(1e5+5)
char buf1[SIZ];
char *p1=buf1,*p2=buf1;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
struct Edge{int v,w,next;};
vector<Edge> vec[N];
int n,m,s,t,now;
int gap[N],h[N],val[N],vis[N];
struct cmp
{
bool operator()(int a,int b)
{return h[a]<h[b];}
};
priority_queue<int,vector<int>,cmp> q;
queue<int> b;
bool bfs()
{
memset(h,0x3f,(n+1)*sizeof(int));
b.push(t);h[t]=0;vis[t]=1;
while(!b.empty())
{
int u=b.front();b.pop();
vis[u]=0;
for(int i=0; i<vec[u].size(); i++)
{
int v=vec[u][i].v,j=vec[u][i].next;
if(vec[v][j].w>0&&h[v]>h[u]+1)
{
h[v]=h[u]+1;
if(!vis[v])
b.push(v),vis[v]=1;
}
}
}
return h[s]!=INF;
}
void relabel(int u)
{
h[u]=INF;
for(int i=0; i<vec[u].size(); i++)
{
int v=vec[u][i].v;
if(vec[u][i].w>0&&h[u]>h[v]+1)
h[u]=h[v]+1;
}
}
int HLPP()
{
if(!bfs())return -1;
h[s]=n;
for(int i=1; i<=n; i++)
if(h[i]!=INF)++gap[h[i]];
for(int i=0; i<vec[s].size(); i++)
{
int v=vec[s][i].v,w=vec[s][i].w,j=vec[s][i].next;
if(w>0)
{
val[s]-=w;
val[v]+=w;
vec[s][i].w-=w;
vec[v][j].w+=w;
if(!vis[v]&&v!=t&&v!=s)
q.push(v),vis[v]=1;
}
}
while(!q.empty())
{
int u=q.top();
q.pop();vis[u]=0;
if(h[u]==INF)continue; // !!!!!!!!!!!
for(int i=0; i<vec[u].size(); i++)
{
int v=vec[u][i].v,j=vec[u][i].next;
if(vec[u][i].w>0&&h[u]==h[v]+1)
{
int w=min(vec[u][i].w,val[u]);
val[u]-=w;
val[v]+=w;
vec[u][i].w-=w;
vec[v][j].w+=w;
if(!vis[v]&&v!=t&&v!=s)
q.push(v),vis[v]=1;
if(!val[u])break;
}
}
if(!val[u])continue;
if(!--gap[h[u]])
{
for(int i=1; i<=n; i++)
if(i!=s&&i!=t&&h[u]<h[i]&&h[i]<=n)
h[i]=n+1;
}
relabel(u);++gap[h[u]];
q.push(u);vis[u]=1;
}
return val[t];
}
signed main()
{
read(n);read(m);read(s);read(t);
for(int i=1,u,v,w; i<=m; i++)
{
read(u);read(v);read(w);
vec[u].push_back({v,w,(int)vec[v].size()});
vec[v].push_back({u,0,(int)vec[u].size()-1});
}
write(HLPP());pc('\n');
return 0;
}有向图最小费用最大流
时间复杂度 \(O(nmf)\) ，其中 \(f\) 为最大流，一般不会被卡。
空间复杂度 \(O(m)\)
- vector写法，C++14 1.41s(O2 542ms)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define N (int)(5e3+10)
#define M (int)(1e6+25)
#define SIZ (int)(1e5+5)
char buf1[SIZ];
char *p1=buf1,*p2=buf1;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
if(k>9)write(k/10);
pc(k%10+'0');
}
struct Edge{int v,w,c,next;};
struct node{int u,i,j;}pre[N];
vector<Edge> vec[N];
int n,m,s,t,flow,cost;
int in[N],d[N],vis[N];
queue<int> q;
bool spfa()
{
memset(d,0x3f,(n+1)*sizeof(int));
memset(in,0x3f,(n+1)*sizeof(int));
memset(vis,0,(n+1)*sizeof(int));
q.push(s);vis[s]=1;d[s]=0;pre[t].u=0;
while(!q.empty())
{
int u=q.front();q.pop();
vis[u]=0;
for(int i=0; i<vec[u].size(); i++)
{
int v=vec[u][i].v,w=vec[u][i].w;
int c=vec[u][i].c,j=vec[u][i].next;
if(w>0&&d[v]>d[u]+c)
{
d[v]=d[u]+c;
pre[v]={u,i,j};
in[v]=min(in[u],w);
if(!vis[v])
q.push(v),vis[v]=1;
}
}
}
return pre[t].u!=0;
}
void Dinic()
{
while(spfa())
{
flow+=in[t];
cost+=in[t]*d[t];
int u,i,j,v=t;
while(v!=s)
{
u=pre[v].u,i=pre[v].i,j=pre[v].j;
vec[u][i].w-=in[t];
vec[v][j].w+=in[t];
v=pre[v].u;
}
}
}
signed main()
{
read(n);read(m);read(s);read(t);
for(int i=1,u,v,w,c; i<=m; i++)
{
read(u);read(v);read(w);read(c);
vec[u].push_back({v,w,c,(int)vec[v].size()});
vec[v].push_back({u,0,-c,(int)vec[u].size()-1});
}
Dinic();
write(flow);pc(' ');write(cost);pc('\n');
return 0;
}- 链式前向星写法，C++14 1.95s(O2 1.45s)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define N (int)(5e3+10)
#define M (int)(1e6+25)
#define SIZ (int)(1e5+5)
char buf1[SIZ];
char *p1=buf1,*p2=buf1;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
if(k>9)write(k/10);
pc(k%10+'0');
}
struct Edge
{
int u,v,w,c,next;
}e[M];
int n,m,s,t,flow,cost;
int pos=1,head[N],in[N],d[N],pre[N],last[N],vis[N];
void addEdge(int u,int v,int w,int c)
{
e[++pos]={u,v,w,c,head[u]};
head[u]=pos;
}
struct node
{
int u,dis;
bool operator<(const node &o)const
{return dis>o.dis;}
};
queue<int> q;
bool spfa()
{
memset(d,0x3f,(n+1)*sizeof(int));
memset(in,0x3f,(n+1)*sizeof(int));
memset(vis,0,(n+1)*sizeof(int));
q.push(s);vis[s]=1;d[s]=0;pre[t]=0;
while(!q.empty())
{
int u=q.front();q.pop();
vis[u]=0;
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].v;
if(e[i].w>0&&d[v]>d[u]+e[i].c)
{
d[v]=d[u]+e[i].c;
pre[v]=u;
last[v]=i;
in[v]=min(in[u],e[i].w);
if(!vis[v])
q.push(v),vis[v]=1;
}
}
}
return pre[t]!=0;
}
void Dinic()
{
while(spfa())
{
flow+=in[t];
cost+=in[t]*d[t];
int at=t;
while(at!=s)
{
e[last[at]].w-=in[t];
e[last[at]^1].w+=in[t];
at=pre[at];
}
}
}
signed main()
{
read(n);read(m);read(s);read(t);
for(int i=1,u,v,w,c; i<=m; i++)
{
read(u);read(v);read(w);read(c);
addEdge(u,v,w,c);addEdge(v,u,0,-c);
}
Dinic();
write(flow);pc(' ');write(cost);pc('\n');
return 0;
}有向图有源汇上下界最大流
例题：P5192 Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流
本例题建模：
- 先建立一个源点
- 从源点到每个少女，流量为 \(\left[G_i,+\infty\right)\)
- 从每个少女到每一天，流量为 \([l_i,r_i]\)
- 从每一天到汇点，流量为 \([0,D_i]\)
然后跑有源汇上下界最大流就好了
- ISAP版 C++14 O2 189ms
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
// #define gc() readchar()
#define gc() getchar()
#define pc(a) putchar(a)
#define N (int)(5e4+15)
#define M (int)(4e5+15)
#define SIZ (int)(1e5+15)
// char buf1[SIZ],*p1=buf1,*p2=buf1;
// char readchar()
// {
// if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
// return p1==p2?EOF:*p1++;
// }
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
struct Edge
{
int u,v,w,next;
}e[M];
int n,m,s,t,s0,t0;
int pos=1,head[N],dep[N],now[N],gap[N],A[N];
void add(int u,int v,int w)
{
e[++pos]={u,v,w,head[u]};head[u]=pos;
e[++pos]={v,u,0,head[v]};head[v]=pos;
}
void addEdge(int u,int v,int l,int r)
{
add(u,v,r-l);
A[u]-=l;A[v]+=l;
}
queue<int> q;
bool bfs()
{
memset(dep,0x3f,(n+m+5)*sizeof(int));
memset(gap,0,(n+m+5)*sizeof(int));
q.push(t0);dep[t0]=1;gap[1]=1;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].v;
if(e[i^1].w&&dep[v]==INF)
{
dep[v]=dep[u]+1;
gap[dep[v]]++;
q.push(v);
}
}
}
return dep[s0]!=INF;
}
int dfs(int u,int in)
{
if(u==t0)return in;
int out=0;
for(int i=now[u]; i&∈ i=e[i].next)
{
int v=e[i].v;now[u]=i;
if(e[i].w&&dep[u]==dep[v]+1)
{
int res=dfs(v,min(in,e[i].w));
e[i].w-=res;
e[i^1].w+=res;
in-=res;
out+=res;
}
if(!in)return out;
}
if(!--gap[dep[u]])dep[s0]=n+m+5;
gap[++dep[u]]++;
return out;
}
int ISAP()
{
if(!bfs())return 0;
int res=0;
while(dep[s0]<=n+m+4)
{
memcpy(now,head,sizeof(head));
res+=dfs(s0,INF);
}
return res;
}
signed main()
{
while(~scanf("%lld%lld",&n,&m))
{
memset(head,0,(n+m+5)*sizeof(int));
memset(A,0,(n+m+5)*sizeof(int));
s=0;t=n+m+1;pos=1;
int tot=0;
for(int i=1; i<=m; i++)
{
int x;read(x);
addEdge(s,i,x,INF);
}
for(int i=1,C,D; i<=n; i++)
{
read(C);read(D);
addEdge(m+i,t,0,D);
for(int j=1,x,L,R; j<=C; j++)
{
read(x);read(L);read(R);
addEdge(x+1,m+i,L,R);
}
}
s0=n+m+2;t0=n+m+3;
for(int i=0; i<=n+m+1; i++)
{
if(A[i]>0)add(s0,i,A[i]),tot+=A[i];
else if(A[i]<0)add(i,t0,-A[i]);
}
add(t,s,INF);
if(ISAP()<tot){puts("-1\n");continue;}
int res=e[pos].w;
e[pos].w=e[pos-1].w=0;
s0=s;t0=t;
write(res+ISAP());puts("\n");
}
return 0;
}无向图无源汇最大流
Stoer-Wagner
斯托瓦格纳?
朴素写法
时间复杂度 \(O(nm+n^3)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+15)
char buf1[SIZ],*p1=buf1,*p2=buf1;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
#define N (int)(666)
int n,m,d[N][N],s,t,dap[N],vis[N],w[N],ord[N];
int proc(int x)
{
memset(vis,0,(n+1)*sizeof(int));
memset(w,0,(n+1)*sizeof(int));
w[0]=-1;
for(int i=1; i<=n-x+1; i++)
{
int mx=0;
for(int j=1; j<=n; j++)
if(!dap[j]&&!vis[j]&&w[j]>w[mx])mx=j;
vis[mx]=1;ord[i]=mx;
for(int j=1; j<=n; j++)
if(!dap[j]&&!vis[j])w[j]+=d[mx][j];
}
s=ord[n-x];t=ord[n-x+1];
return w[t];
}
int sw()
{
int res=INF;
for(int i=1; i<n; i++)
{
res=min(res,proc(i));
dap[t]=1;
for(int j=1; j<=n; j++)
{
d[s][j]+=d[t][j];
d[j][s]+=d[j][t];
}
}
return res;
}
signed main()
{
read(n);read(m);
for(int i=1,u,v,w; i<=m; i++)
{
read(u);read(v);read(w);
d[u][v]+=w;d[v][u]+=w;
}
write(sw());pc('\n');
return 0;
}堆优化（意义不大）
时间复杂度 \(O(nm+n^2\log n)\)
还没写
最小树形图
最小树形图 朱刘算法
时间复杂度 \(O(nm)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+15)
char buf1[SIZ],*p1=buf1,*p2=buf1;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
#define M (int)(1e4+15)
#define N (int)(1e3+5)
struct Edge
{
int u,v,w,next;
}e[M];
int n,m,rt;
int pre[N],ine[N];
int vis[N],id[N];
int pos=1,head[N];
void addEdge(int u,int v,int w)
{
e[++pos]={u,v,w,head[u]};
head[u]=pos;
}
int solve()
{
int ans=0;
while(1)
{
for(int i=1; i<=n; i++)
ine[i]=INF;
for(int i=2; i<=pos; i++)
{
int u=e[i].u,v=e[i].v;
if(u!=v&&e[i].w<ine[v])
ine[v]=e[i].w,pre[v]=u;
}
for(int i=1; i<=n; i++)
if(i!=rt&&ine[i]==INF)return INF;
int cnt=0;
for(int i=1; i<=n; i++)
vis[i]=id[i]=0;
for(int i=1; i<=n; i++)
{
if(i==rt)continue;
ans+=ine[i];
int v=i;
while(vis[v]!=i&&!id[v]&&v!=rt)
{
vis[v]=i;
v=pre[v];
}
if(!id[v]&&v!=rt)
{
id[v]=++cnt;
for(int u=pre[v]; u!=v; u=pre[u])
id[u]=cnt;
}
}
if(!cnt)break;
for(int i=1; i<=n; i++)
if(!id[i])id[i]=++cnt;
for(int i=2; i<=pos; i++)
{
int u=e[i].u,v=e[i].v;
e[i].u=id[u];e[i].v=id[v];
if(id[u]!=id[v])e[i].w-=ine[v];
}
rt=id[rt];
n=cnt;
}
return ans;
}
signed main()
{
read(n);read(m);read(rt);
for(int i=1,u,v,w; i<=m; i++)
{
read(u);read(v);read(w);
addEdge(u,v,w);
}
int res=solve();
write(res==INF?-1:res);pc('\n');
return 0;
}最小树形图 Tarjan的DMST
时间复杂度 \(O(m+n\log m)\)
代码如下
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+15)
char buf1[SIZ],*p1=buf1,*p2=buf1;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
#define N (int)(2e3+15)
#define M (int)(2e4+15)
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
int n,m,r,cnt,f[N];
int vis[N],stk[N],top;
queue<int> q[N];
namespace leftist
{
struct node
{
int ch[2],u,v,w,dist,tag;
}t[M];
int tot,rt[M];
int New(int u,int v,int w)
{
t[++tot]={0,0,u,v,w};
return tot;
}
void push_down(int x)
{
t[ls(x)].tag+=t[x].tag;
t[ls(x)].w+=t[x].tag;
t[rs(x)].tag+=t[x].tag;
t[rs(x)].w+=t[x].tag;
t[x].tag=0;
}
int merge(int x,int y)
{
if(!x||!y)return x|y;
push_down(x);push_down(y);
if(t[x].w>t[y].w)swap(x,y);
rs(x)=merge(rs(x),y);
if(t[rs(x)].dist>t[ls(x)].dist)
swap(ls(x),rs(x));
t[x].dist=t[rs(x)].dist+1;
return x;
}
int remove(int x)
{
push_down(x);
return merge(ls(x),rs(x));
}
void build()
{
for(int i=1; i<=n; i++)
{
if(q[i].empty())continue;
while(q[i].size()!=1)
{
int p1=q[i].front();q[i].pop();
int p2=q[i].front();q[i].pop();
p1=merge(p1,p2);
q[i].push(p1);
}
if(!q[i].empty())
{
rt[i]=merge(rt[i],q[i].front());
q[i].pop();
}
}
}
}
int find(int x){return f[x]==x?f[x]:f[x]=find(f[x]);}
signed main()
{
using namespace leftist;
read(n);read(m);read(r);
for(int i=1,u,v,w; i<=m; i++)
{
read(u);read(v);read(w);
int p=New(u,v,w);
q[v].push(p);
// rt[v]=merge(rt[v],p);
}
for(int i=1; i<=n; i++)
{
int p=New(i>1?i-1:n,i,INF);
q[i].push(p);
// rt[i]=merge(rt[i],p);
}
build();
for(int i=1; i<=2*n; i++)f[i]=i;
stk[++top]=r;vis[r]=1;
int ans=0,cnt=n;
while(rt[stk[top]])
{
int &p=rt[stk[top]];
int u=find(t[p].u);
if(u==stk[top])
{
p=remove(p);
continue;
}
if(!vis[u])
{
stk[++top]=u;
vis[u]=1;
continue;
}
int q=++cnt;
while(vis[u])
{
int v=stk[top--];
vis[v]=0;f[v]=q;
node *tmp=&t[rt[v]];
tmp->tag-=tmp->w;
if(find(tmp->v)!=find(r))
ans+=tmp->w;
rt[v]=remove(rt[v]);
rt[q]=merge(rt[q],rt[v]);
}
stk[++top]=q;
vis[q]=1;
}
ans=ans>=INF?-1:ans;
write(ans);pc('\n');
return 0;
}改了一下范围是这样的
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+15)
char buf1[SIZ],*p1=buf1,*p2=buf1;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
#define N (int)(2e5+15)
#define M (int)(2e6+15)
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
int n,m,r,cnt,f[N];
int vis[N],stk[N],top;
queue<int> q[N];
namespace leftist
{
struct node
{
int ch[2],u,v,w,dist,tag;
}t[M];
int tot,rt[M];
int New(int u,int v,int w)
{
t[++tot]={0,0,u,v,w};
return tot;
}
void push_down(int x)
{
t[ls(x)].tag+=t[x].tag;
t[ls(x)].w+=t[x].tag;
t[rs(x)].tag+=t[x].tag;
t[rs(x)].w+=t[x].tag;
t[x].tag=0;
}
int merge(int x,int y)
{
if(!x||!y)return x|y;
push_down(x);push_down(y);
if(t[x].w>t[y].w)swap(x,y);
rs(x)=merge(rs(x),y);
if(t[rs(x)].dist>t[ls(x)].dist)
swap(ls(x),rs(x));
t[x].dist=t[rs(x)].dist+1;
return x;
}
int remove(int x)
{
push_down(x);
return merge(ls(x),rs(x));
}
void build()
{
for(int i=1; i<=n; i++)
{
if(q[i].empty())continue;
while(q[i].size()!=1)
{
int p1=q[i].front();q[i].pop();
int p2=q[i].front();q[i].pop();
p1=merge(p1,p2);
q[i].push(p1);
}
if(!q[i].empty())
{
rt[i]=merge(rt[i],q[i].front());
q[i].pop();
}
}
}
}
int find(int x){return f[x]==x?f[x]:f[x]=find(f[x]);}
signed main()
{
using namespace leftist;
read(n);read(m);read(r);
for(int i=1,u,v,w; i<=m; i++)
{
read(u);read(v);read(w);
int p=New(u,v,w);
q[v].push(p);
// rt[v]=merge(rt[v],p);
}
for(int i=1; i<=n; i++)
{
int p=New(i>1?i-1:n,i,INF);
q[i].push(p);
// rt[i]=merge(rt[i],p);
}
build();
for(int i=1; i<=2*n; i++)f[i]=i;
stk[++top]=r;vis[r]=1;
int ans=0,cnt=n;
while(rt[stk[top]])
{
int &p=rt[stk[top]];
int u=find(t[p].u);
if(u==stk[top])
{
p=remove(p);
continue;
}
if(!vis[u])
{
stk[++top]=u;
vis[u]=1;
continue;
}
int q=++cnt;
while(vis[u])
{
int v=stk[top--];
vis[v]=0;f[v]=q;
node *tmp=&t[rt[v]];
tmp->tag-=tmp->w;
if(find(tmp->v)!=find(r))
ans+=tmp->w;
rt[v]=remove(rt[v]);
rt[q]=merge(rt[q],rt[v]);
}
stk[++top]=q;
vis[q]=1;
}
ans=ans>=INF?-1:ans;
write(ans);pc('\n');
return 0;
}二分图
二分图最大匹配
匈牙利算法
时间复杂度 \(O(nm)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e3+5)
#define M (int)(1e5+15)
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e6+5)
char buf1[SIZ],*p1=buf1,*p2=buf1;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc(); T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
int n1,n2,m,vis[N],mch[N],ans;
vector<int> vec[N];
bool dfs(int u,int now)
{
if(vis[u]==now)return 0;
vis[u]=now;
for(int v:vec[u])
if(!mch[v]||dfs(mch[v],now))
{
mch[v]=u;
return 1;
}
return 0;
}
signed main()
{
read(n1);read(n2);read(m);
for(int i=1,u,v; i<=m; i++)
{
read(u);read(v);
vec[u].push_back(v);
}
for(int i=1; i<=n1; i++)
ans+=dfs(i,i);
write(ans);pc('\n');
return 0;
}ISAP
时间复杂度 \(O(m\sqrt{n})\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e3+5)
#define M (int)(5e4+15)
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e6+5)
char buf1[SIZ],*p1=buf1,*p2=buf1;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
struct Edge
{
int u,v,w,next;
}e[M<<3];
int n1,n2,m,pos=1,ans,head[N],now[N],s,t,gap[N],dep[N];
void addEdge(int u,int v,int w)
{
e[++pos]={u,v,w,head[u]};
head[u]=pos;
}
queue<int> q;
void bfs()
{
memset(dep,0x3f,sizeof(dep));
q.push(t);dep[t]=1;gap[1]=1;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].v;
if(e[i^1].w>0&&dep[v]==INF)
{
dep[v]=dep[u]+1;
gap[dep[v]]++;
q.push(v);
}
}
}
}
int dfs(int u,int in)
{
if(u==t)return in;
int out=0;
for(int i=now[u]; i; i=e[i].next)
{
int v=e[i].v;now[u]=i;
if(e[i].w>0&&dep[u]==dep[v]+1)
{
int res=dfs(v,min(in,e[i].w));
e[i].w-=res;
e[i^1].w+=res;
in-=res;
out+=res;
}
if(!in)return out;
}
if(!--gap[dep[u]])dep[s]=n1+n2+3;
gap[++dep[u]]++;
return out;
}
signed main()
{
read(n1);read(n2);read(m);
s=1;t=n1+n2+2;
for(int i=1,u,v; i<=m; i++)
{
read(u);read(v);
addEdge(u+1,v+n1+1,1);addEdge(v+n1+1,u+1,0);
}
for(int i=1; i<=n1; i++)
addEdge(s,i+1,1),addEdge(i+1,s,0);
for(int i=1; i<=n2; i++)
addEdge(n1+i+1,t,1),addEdge(t,n1+i+1,0);
bfs();
while(dep[s]<=n1+n2+2)
memcpy(now,head,sizeof(head)),
ans+=dfs(s,INF);
write(ans);pc('\n');
return 0;
}二分图最大权完美匹配
二分图最大权匹配可以用费用流来做，时间复杂度仍为 \(\mathcal{O}(nmf)\) ，代码还木有。
KM算法
时间复杂度 \(O(n^3)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(555)
int n,m;
int g[N][N],slack[N];
int lx[N],ly[N],px[N],py[N],pre[N],d;
bool vx[N],vy[N];
void aug(int v)
{
int t;
while(v)
{
t=px[pre[v]];
px[pre[v]]=v;
py[v]=pre[v];
v=t;
}
}
queue<int> q;
void bfs(int s)
{
memset(vx,0,sizeof(vx));
memset(vy,0,sizeof(vy));
for(int i=1; i<=n; i++)
slack[i]=INF;
while(!q.empty())q.pop();
q.push(s);
while(1)
{
while(!q.empty())
{
int u=q.front();q.pop();
vx[u]=1;
for(int i=1; i<=n; i++)
{
if(!vy[i]&&lx[u]+ly[i]-g[u][i]<slack[i])
{
slack[i]=lx[u]+ly[i]-g[u][i];
pre[i]=u;
if(!slack[i])
{
vy[i]=1;
if(!py[i]){aug(i);return;}
else q.push(py[i]);
}
}
}
}
int d=INF;
for(int i=1; i<=n; i++)
if(!vy[i])d=min(d,slack[i]);
for(int i=1; i<=n; i++)
{
if(vx[i])lx[i]-=d;
if(vy[i])ly[i]+=d;
else slack[i]-=d;
}
for(int i=1; i<=n; i++)
{
if(!vy[i]&&!slack[i])
{
vy[i]=1;
if(!py[i]){aug(i);return;}
else q.push(py[i]);
}
}
}
}
int KM()
{
int res=0;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
lx[i]=max(lx[i],g[i][j]);
for(int i=1; i<=n; i++)bfs(i);
for(int i=1; i<=n; i++)
res+=g[py[i]][i];
return res;
}
signed 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]=-INF;
for(int i=1,u,v,w; i<=m; i++)
{
cin >> u >> v >> w;
g[u][v]=max(g[u][v],w);
}
cout << KM() << endl;
for(int i=1; i<=n; i++)
cout << py[i] << " \n"[i==n];
return 0;
}一般图最大匹配
带花树算法
时间复杂度 \(O(n^3)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e3+15)
int n,m,cnt,vis[N];
int mch[N],pre[N],f[N],col[N];
vector<int> vec[N];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
queue<int> q;
void aug(int v)
{
int t;
while(v)
{
t=mch[pre[v]];
mch[v]=pre[v];
mch[pre[v]]=v;
v=t;
}
}
int lca(int u,int v)
{
++cnt;
u=find(u);v=find(v);
while(vis[u]!=cnt)
{
vis[u]=cnt;
u=find(pre[mch[u]]);
if(v)swap(u,v);
}
return u;
}
void shrink(int u,int v,int p)
{
while(find(u)!=p)
{
pre[u]=v;
v=mch[u];
if(col[v]==2)
col[v]=1,q.push(v);
f[u]=p;f[v]=p;
u=pre[v];
}
}
bool bfs(int s)
{
for(int i=1; i<=n; i++)
f[i]=i,pre[i]=col[i]=0;
while(!q.empty())q.pop();
q.push(s);col[s]=1;
while(!q.empty())
{
int u=q.front();q.pop();
for(int v:vec[u])
{
if(!col[v])
{
pre[v]=u;
if(!mch[v]){aug(v);return 1;}
else col[v]=2,col[mch[v]]=1,q.push(mch[v]);
}else if(col[v]==1&&find(u)!=find(v))
{
int p=lca(u,v);
shrink(u,v,p);shrink(v,u,p);
}
}
}
return 0;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i=1,u,v; i<=m; i++)
{
cin >> u >> v;
vec[u].push_back(v);
vec[v].push_back(u);
}
int res=0;
for(int i=1; i<=n; i++)
res+=!mch[i]&&bfs(i);
cout << res << endl;
for(int i=1; i<=n; i++)
cout << mch[i] << " \n"[i==n];
return 0;
}一般图最大权匹配
不会 qwq 感觉要等到我大学才会去学，咕咕咕...
无向图的最小环问题
下面这个代码求的是至少包含 \(3\) 个点的环
要根据题意判断
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f
int n,m,ans=INF;
int g[105][105],f[105][105];
signed main()
{
ios::sync_with_stdio(0);
cin >> n >> m;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
g[i][j]=f[i][j]=INF;
for(int i=1,u,v,w; i<=m; i++)
{
cin >> u >> v >> w;
g[u][v]=min(g[u][v],w);
g[v][u]=min(g[v][u],w);
f[u][v]=min(f[u][v],w);
f[v][u]=min(f[v][u],w);
}
for(int k=1; k<=n; k++)
{
for(int i=1; i<k; i++)
for(int j=i+1; j<k; j++)
ans=min(ans,f[i][j]+g[i][k]+g[k][j]);
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
if(ans==INF)cout << "No solution.";
else cout << ans;
return 0;
}点分治
时间复杂度 \(\mathcal{O}(n \log n)\)
// 2024年05月26日 19:08:34
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e4 + 15))
#define M ((int)(115))
#define K ((int)(1e7 + 15))
int n, m, rt, rt_fa, sum, pos = 1, head[N], sz[N], mx[N], qry[N];
int tot, q[N], val[N], dis[N]; char ans[M], vis[N], pd[K];
struct Edge { int u, v, w, next; } e[N * 2];
void addEdge(int u, int v, int w) {
e[++pos] = {u, v, w, head[u]}; head[u] = pos;
}
void getroot(int u, int fa)
{
mx[u] = 0; sz[u] = 1;
for(int i = head[u]; i; i = e[i].next)
{
int v = e[i].v; if(v == fa || vis[v]) continue;
getroot(v, u); sz[u] += sz[v]; up(mx[u], sz[v]);
}
up(mx[u], sum - sz[u]); if(mx[u] < mx[rt]) { rt = u, rt_fa = fa; }
}
void getdis(int u, int fa)
{
if(dis[u] > 10000000) return;
val[++tot] = dis[u];
for(int i = head[u]; i; i = e[i].next)
{
int v = e[i].v; if(v == fa || vis[v]) continue;
dis[v] = dis[u] + e[i].w; getdis(v, u);
}
}
void init(int u)
{
int c = 0;
for(int i = head[u]; i; i = e[i].next)
{
int v = e[i].v; if(vis[v]) continue;
tot = 0; dis[v] = e[i].w; getdis(v, u);
for(int j = 1; j <= tot; j++)
for(int k = 1; k <= m; k++)
if(qry[k] >= val[j]) ans[k] |= pd[qry[k] - val[j]];
for(int j = 1; j <= tot; j++) { q[++c] = val[j], pd[val[j]] = true; }
}
for(int i = 1; i <= c; i++) pd[q[i]] = false;
}
void solve(int u)
{
vis[u] = pd[0] = true; init(u);
for(int i = head[u]; i; i = e[i].next)
{
int v = e[i].v; if(vis[v]) continue;
sum = v == rt_fa ? n - sz[u] : sz[v];
mx[rt = rt_fa = 0] = n; getroot(v, u); solve(rt);
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> m;
for(int i = 1, u, v, w; i < n; i++)
{
cin >> u >> v >> w;
addEdge(u, v, w); addEdge(v, u, w);
}
for(int i = 1; i <= m; i++) cin >> qry[i];
mx[rt = rt_fa = 0] = sum = n;
getroot(1, 0); solve(rt);
for(int i = 1; i <= m; i++) cout << (ans[i] ? "AYE" : "NAY") << '\n';
return 0;
}参考文献：
