标签：主函数 链表 www 额外 最大 复杂 最大流 algo mes
n为节点数量，m为边数量
EK算法复杂度：O(n*m^2)
dinic算法复杂度：O(n^2*m)
EK算法思想就是先用bfs找到一条增广路（从源点到汇点有流量的路），然后用pre数组记录这条路径上每一个节点的上一个节点。之后利用pre数组完成对这条路上所有边流量的消减，以及增加答案。看代码就清楚了，不复杂
例题：https://www.luogu.com.cn/problem/P3376
EK算法：
#include
#include
#include string.h>
#include
#include set>
#include
#include
EK算法另外一种
// #include //这个是链表版，这道题卡内存不能用链表
// #include // #include // #include // #include // #include // #include // #include
// #define lson rt // #define rson rt // using namespace std;
// typedef long long ll;
// const int INF = 0x3f3f3f3f;
// const int maxm = 20000 + 10; //边的数量
// const int maxn = 200+10; //点的数量
// struct Edge
// {
// int v, w,next;
// } e[maxm];
// int cnt, n, m, st, en,head[maxn],dis[maxn];
// queuer;
// inline void add_edge(int u,int v,int w){
// e[cnt].v=v;
// e[cnt].w=w;
// e[cnt].next=head[u];
// head[u]=cnt++;
// e[cnt].v=u;
// e[cnt].w=0;
// e[cnt].next=head[v];
// head[v]=cnt++;
// }
// int bfs(){
// while(!r.empty()) r.pop();
// memset(dis,0,sizeof(dis));
// r.push(st);
// dis[st]=1;
// while(!r.empty()){
// int u=r.front();
// r.pop();
// for(int i=head[u];i!=-1;i=e[i].next){
// int v=e[i].v;
// if(!dis[v] && e[i].w>0){
// dis[v]=dis[u]+1;
// if(v==en) return 1;
// r.push(v);
// }
// }
// }
// return 0;
// }
// int dfs(int u,int flow){
// if(u==en) return flow;
// int k,tmp=flow;
// for(int i=head[u];i!=-1;i=e[i].next){
// int v=e[i].v;
// if(dis[v]==dis[u]+1 && e[i].w>0){
// k=dfs(v,min(tmp,e[i].w));
// if(!k) dis[v]=0;
// tmp-=k;e[i].w-=k;e[i^1].w+=k;
// if(!tmp) break;
// }
// }
// return flow-tmp;
// }
// void init(){
// cnt=0;
// memset(head,-1,sizeof(head));
// }
// int main()
// {
// init();
// scanf("%d%d%d%d", &n, &m,&st,&en);
// while (m--)
// {
// int u,v,w;
// scanf("%d%d%d",&u,&v,&w);
// add_edge(u,v,w);
// }
// int res=0;
// while(bfs()){
// res+=dfs(st,INF);
// }
// printf("%d\n",res);
// return 0;
// }
#include
#include
#include string.h>
#include
#include set>
#include
#include
dinic算法：
它就是利用bfs对图进行一个分层，然后通过dfs来增广.增广过程除了当前节点x外，还需要传入一个表示“目前为止所有边的最小残量”的limit,当前节点x为汇点或者limit==0时终止dfs过程，否则会多路增广。还有在dfs过程中的一个重要优化：保存每个节点x正在遍历的子边保存在cur[x]以免重复计算遍历过的子边.
cur数组原理是什么呢？其实就是当我们在对一个节点u（假设有多个儿子）进行增广时，把他的儿子1，2的可用流量都用完了，那么在下一次dfs模块走到u时，我们如果可以直接从儿子3开始进行增广就可以大大减少额外的时间开销
cur数组实现:我们可以在dfs里面做一点改动，即先定义一个cur数组，在dfs之前把邻接表的head数组拷贝到cur里面，然后在遍历u的时候同时把cur里面的边的下标后移，以达到将用完的边略去的目的
dinic算法：
#include
#includestring.h>
#include
#include
#includeusing namespace std;
const int maxn=10000;
const int INF=0x3f3f3f3f;
int head[maxn],cnt,st,en,dis[maxn],cur[maxn];
struct edge
{
int v,next,c,flow;
}e[maxn];
void add_edge(int x,int y,int z)
{
e[cnt].v=y;
e[cnt].c=z;
e[cnt].flow=0;
e[cnt].next=head[x];
head[x]=cnt++;
}
bool bfs()
{
memset(dis,0,sizeof(dis));
dis[st]=1;
queueint>r;
r.push(st);
while(!r.empty())
{
int x=r.front();
r.pop();
for(int i=head[x];i!=-1;i=e[i].next)
{
int v=e[i].v;
if(!dis[v] && e[i].c>e[i].flow)
{
dis[v]=dis[x]+1;
r.push(v);
}
}
}
return dis[en];
}
int dinic(int s,int limit)
{
if(s==en || !limit) return limit;
int ans=0;
for(int &i=cur[s];i!=-1;i=e[i].next)
{
int v=e[i].v,feed;
if(dis[v]!=dis[s]+1) continue;
feed=dinic(v,min(limit,e[i].c-e[i].flow));
if(feed)
{
e[i].flow+=feed;
e[i^1].flow-=feed;
limit-=feed;
ans+=feed;
if(limit==0) break;
}
}
if(!ans) dis[s]=-1;
return ans;
}
int main()
{
memset(head,-1,sizeof(head));
int n,f,d;
scanf("%d%d%d",&n,&f,&d);
st=0;
en=2*n+f+d+1;
for(int i=1;ii)
{
add_edge(st,2*n+i,1);
add_edge(2*n+i,st,0);
}
for(int i=1;ii)
{
add_edge(2*n+f+i,en,1);
add_edge(en,2*n+f+i,0);
}
for(int i=1;ii)
{
add_edge(i,n+i,1);
add_edge(n+i,i,0);
int sum1,sum2;
scanf("%d%d",&sum1,&sum2);
int x;
for(int j=0;jj)
{
scanf("%d",&x);
add_edge(x+2*n,i,1);
add_edge(i,x+2*n,0);
}
for(int j=0;jj)
{
scanf("%d",&x);
add_edge(n+i,x+f+2*n,1);
add_edge(x+f+2*n,n+i,0);
}
}//主函数从开头到这就是建图
int ans=0;
while(bfs())
{
for(int i=0;i)
cur[i]=head[i];
ans+=dinic(st,1); //这个1也可以改成无穷大
}
printf("%d\n",ans);
return 0;
}
最大流ek算法和dinic算法总结
标签：主函数 链表 www 额外 最大 复杂 最大流 algo mes
原文地址：https://www.cnblogs.com/kongbursi-2292702937/p/14585252.html