做书封面的网站,北京电商网站建设哪家好,wordpress托管套餐,做齐鲁油官方网站Dinic算法的时间复杂度为O#xff08;n^2m#xff09;。实际运用远远小于这个上界。 特别的#xff0c;Dinic算法求解二分图最大匹配的时间复杂度为O#xff08;msqrt#xff08;n#xff09;#xff09; 最大流问题模板
#include bits/stdc.h
using namespace…Dinic算法的时间复杂度为On^2m。实际运用远远小于这个上界。 特别的Dinic算法求解二分图最大匹配的时间复杂度为Omsqrtn 最大流问题模板
#include bits/stdc.h
using namespace std;
const int N 10010,M 200010, INF 1e8;
int n,m,S,T;
int h[N],ne[M],e[M],f[M],idx;
int d[N],q[N],cur[N];
void add(int a,int b,int c)
{e[idx] b,f[idx] c,ne[idx] h[a],h[a] idx;e[idx] a,f[idx] 0,ne[idx] h[b],h[b] idx;
}
bool bfs()
{int hh 0, tt 0;memset(d, -1, sizeof d);q[0] S, d[S] 0, cur[S] h[S];while (hh tt){int t q[hh ];for (int i h[t]; ~i; i ne[i]){int ver e[i];if (d[ver] -1 f[i]){d[ver] d[t] 1;cur[ver] h[ver];if (ver T) return true;q[ tt] ver;}}}return false;
}
int find(int u,int limit)
{if (uT) return limit;int flow 0;for (int i cur[u];~iflowlimit;i ne[i]){cur[u] i;//当前弧优化int ver e[i];if (d[ver] d[u]1f[i]){int t find(ver,min(f[i],limit-flow));if (!t) d[ver] -1;f[i] - t,f[i^1] t,flowt;}}return flow;
}
int dinic()
{int r 0,flow;while (bfs()) while (flow find(S,INF)) r flow;return r;
}
int main()
{scanf(%d%d%d%d,n,m,S,T);memset(h,-1,sizeof h);while (m--){int a,b,c;scanf(%d%d%d,a,b,c);add(a,b,c);}printf(%d\n,dinic());return 0;
}应用一二分图匹配问题 飞行员配对方案问题 https://www.acwing.com/problem/content/2177/
int main()
{scanf(%d%d,m,n);S 0,T n1;memset(h,-1,sizeof h);for (int i 1;im;i) add(S,i,1);for (int i m1;in;i) add(i,T,1);int a,b;while (scanf(%d%d,a,b),a!-1) add(a,b,1);printf(%d\n,dinic());for (int i0;iidx;i2)if (e[i]me[i]n!f[i]) printf(%d %d\n,e[i^1],e[i]);return 0;
}应用二无源汇的最大流问题 无源汇上下界可行流 https://www.acwing.com/problem/content/2190/) 注意流量守恒
int main()
{memset(h,-1,sizeof h);scanf(%d%d,n,m);S 0,T n1,tot 0;for (int i0;im;i){int a,b,c,d;scanf(%d%d%d%d,a,b,c,d);add(a,b,c,d);A[a] - c,A[b] c;//出去c进来c}for (int i1;in;i){if (A[i]0) add(S,i,0,A[i]),tot A[i];//如果进来大于0else if (A[i]0) add(i,T,0,-A[i]);//如果出去}if (dinic()!tot) printf(NO\n);//如果最低的流量都不行else {printf(YES\n);for (int i0;im*2;i2)printf(%d\n,f[i^1]l[i]);//输出方案}return 0;
}应用三有源汇的最大流问题 有源汇上下界最大流 https://www.acwing.com/problem/content/2191/ 先链接一个t到s的边看是否能满足所有边的最小下限 如果满足再做一次dinic()
int main()
{memset(h,-1,sizeof h);int s,t,tot 0;scanf(%d%d%d%d,n,m,s,t);S 0,T n1;while (m--){int a,b,c,d;scanf(%d%d%d%d,a,b,c,d);add(a,b,d-c);A[a] - c,A[b] c;}for (int i1;in;i)if (A[i]0) add(S,i,A[i]),tot A[i];else if (A[i]0) add(i,T,-A[i]);add(t,s,INF);if (dinic()tot) puts(No Solution);else {int res f[idx-1];f[idx-1] f[idx-2] 0;S s,T t;printf(%d,resdinic());}
}应用四有源汇的最小流问题 有源汇上下界最小流 https://www.acwing.com/problem/content/2192/ 加t到s的边然后dinic然后再反向dinic
int main()
{memset(h,-1,sizeof h);int s,t,tot 0;scanf(%d%d%d%d,n,m,s,t);S 0,T n1;while (m--){int a,b,c,d;scanf(%d%d%d%d,a,b,c,d);add(a,b,d-c);A[a] - c,A[b] c;}for (int i1;in;i)if (A[i]0) add(S,i,A[i]),tot A[i];else if (A[i]0) add(i,T,-A[i]);add(t,s,INF);if (dinic()tot) puts(No Solution);else {int res f[idx-1];f[idx-1] f[idx-2] 0;S t,T s;printf(%d,res-dinic());}
}应用五多源汇的最大流问题 多源汇最大流 https://www.acwing.com/problem/content/2236/
int main()
{memset(h,-1,sizeof h);int ss,tt;scanf(%d%d%d%d,n,m,ss,tt);S 0,T n1;while (ss--){int x;scanf(%d,x);add(S,x,INF);}while (tt--){int x;scanf(%d,x);add(x,T,INF);}while (m--){int a,b,c;scanf(%d%d%d,a,b,c);add(a,b,c);}printf(%d\n,dinic());
}应用六关键边 伊基的故事 I - 道路重建 https://www.acwing.com/problem/content/2238/ dinic后从S和T遍历
void dfs(int u, bool st[], int t)
{st[u] true;for (int i h[u]; ~i; i ne[i]){int j i ^ t, ver e[i];if (f[j] !st[ver])dfs(ver, st, t);}
}
int main()
{memset(h,-1,sizeof h);scanf(%d%d,n,m);for (int i 0;im;i){int a,b,c;scanf(%d%d%d,a,b,c);add(a,b,c);}S 0,T n-1;dinic();dfs(S, vis_s, 0);dfs(T, vis_t, 1);int res 0;for (int i 0; i m * 2; i 2)if (!f[i] vis_s[e[i ^ 1]] vis_t[e[i]])res ;printf(%d\n, res);return 0;
}应用七有边大小使用限制的最大流判定 秘密挤奶机 https://www.acwing.com/problem/content/2279/
bool check(int x)
{for (int i0;iidx;i) if (w[i]x) f[i] 0;else f[i] 1;return dinic()k;
}
int main()
{memset(h,-1,sizeof h);scanf(%d%d%d,n,m,k);S 1,T n;for (int i 0;im;i){int a,b,c;scanf(%d%d%d,a,b,c);add(a,b,c);}int l 1,r 1e6;while (lr){int mid lr1;if (check(mid)) r mid;else l mid1;}printf(%d\n,r);return 0;
}应用八拆点 餐饮 https://www.acwing.com/problem/content/2242/
int main()
{memset(h,-1,sizeof h);scanf(%d%d%d,n,m,k);S 0,T 2*nmk1;for (int i 2*n1;i2*nm;i) add(S,i,1);for (int i 1;in;i) add(i,in,1);for (int i 2*nm1;i2*nmk;i) add(i,T,1);for (int i 1;in;i){int a,b,x;scanf(%d%d,a,b);for (int j 0;ja;j){scanf(%d,x);add(2*nx,i,1);}for (int j 0;jb;j){scanf(%d,x);add(ni,2*nmx,1);}}printf(%d\n,dinic());return 0;
}
