锐客网

  1. 首页 > it技术 > >

Acm|网络流-EK算法

ACM网络流

【Acm|网络流-EK算法】EK算法的思路：
基于贪心的思想，每次选取一条起点到终点的路径，毋庸置疑，这条路的流量就等于这条路径上的权值是最小值。将这条路的权值都减去流量，再将路径的反向边加上流量（这样可以就给贪心一次反悔的机会），无限循环以上步骤，到找不到任何一条起点到终点的路，最后所有的最小值加起来就是最大流了。
（这只是我对EK算法的总结，学习网络流还是去看别人的博客吧）
代码：

#include #include #include #include #define LL long long #define Max 100005 const LL mod=1e9+7; const LL LL_MAX=9223372036854775807; using namespace std; struct node { int v,next; LL w; }edge[Max]; //使用邻接表存边 int n,m; int pre[Max],head[Max],rec[Max]; //pre保存路径，rec保存该点在邻接表中的位置，head邻接表的指针 LL flow[Max]; //记录最小值 int no; queueq; void init() { no=0; memset(head,-1,sizeof(head)); } void add(int u,int v,LL c){ edge[no].v=v,edge[no].w=c; edge[no].next=head[u],head[u]=no++; edge[no].v=u; edge[no].w=0; edge[no].next=head[v],head[v]=no++; }LL bfs(int st,int en)//寻找st-->en的路径 { memset(pre,-1,sizeof(pre)); while(!q.empty())q.pop(); pre[st]=st,flow[st]=INT_MAX; q.push(st); while(!q.empty()){ int top=q.front(); q.pop(); int now=head[top]; while(now!=-1){ int t=edge[now].v; if(pre[t]==-1 && edge[now].w>0){//该点没有被访问过，且权值不为0 flow[t]=min(flow[top],edge[now].w); pre[t]=top; rec[t]=now; q.push(t); } now=edge[now].next; } if(pre[en]!=-1) return flow[en]; } return -1; } LL EK(int st,int en) { LL ans=0; LL add; while((add=bfs(st,en))!=-1){//走遍所有st-->en的路径 ans+=add; int k=en; // printf("%d\n",add); while(k!=pre[k]){ edge[rec[k]].w-=add; //权值减去最小值 edge[rec[k]^1].w+=add; //反向边加上最小值 //printf("%d\n",k); k=pre[k]; } } return ans; } int main() { int x,y; LL c; while(scanf("%d%d",&m,&n)==2){ init(); for(int i=0; i

    推荐阅读


    上一篇：滴滴-2019+快手2020（A）-校园招聘算法工程师笔试题

    下一篇：GIT|python操作git相关命令