首页 > 代码库 > 图论——最大流(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)