首页 > 代码库 > 图论——最大流(DINIC)
图论——最大流(DINIC)
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define INF 0x3f3f3f3fusing namespace std;int dis[300];//BFS深度int q[30000],h,r;//BFS队列int e;//终点int head[300];//邻接表头指针int current[300];//当前弧优化struct edge{ int to,v; int next;}E[333333];int tot;void addedge(int a,int b,int v){ E[tot].to = b; E[tot].v = v; E[tot].next = head[a]; head[a] = tot++; E[tot].to = a; E[tot].v = 0; E[tot].next = head[b]; head[b] = tot++;}void init(){ memset(E,0,sizeof(E)); memset(head,-1,sizeof(head)); tot = 0;}int BFS(int b){ int u; memset(dis,-1,sizeof(dis)); dis[b] = 0; h = 0; r=1; q[1] = b; while(h < r) { u = q[++h]; for (int i = head[u]; i!=-1;i = E[i].next) { int v = E[i].to; if (dis[v] < 0&&E[i].v > 0) { dis[v] = dis[u]+1; q[++r] = v; } } } if (dis[e]>0) return 1; else return 0;}int dinic(int x ,int low){ int i,a = 0; if (x==e) return low; for (i = current[x]; i !=-1 ; i = E[i].next) { current[x] = i; int v = E[i].to; if (E[i].v > 0&&dis[v]==dis[x]+1 && (a=dinic(v,min(low,E[i].v)))) { E[i].v -= a; E[i^1].v += a; return a; } } return 0;}int main(){
int t;int ANS; init();
int b = ?//起点main局部变量
e = ?//全局变量
int tans; while(BFS(b)) { for (int i = 0; i<=e;i++) current[i] = head[i]; while (tans = dinic(b,0x3f3f3f3f)) ANS+=tans; }
cout << ANS <<endl; return 0;}
图论——最大流(DINIC)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。