网络流相关模板

发表于 分类于

包含 Dinic 费用流 无/有源汇网络流

网络流 Dinic: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
struct edge
{
    int v,nxt,flow;
}e[5000005];

int ecnt,head[100005];

void adde(int u,int v,int flow)
{
    e[ecnt].v = v;
    e[ecnt].nxt = head[u];
    head[u] = ecnt;
    e[ecnt].flow = flow;
    ecnt++;
}

int s,t;
int dep[100050];

bool bfs()
{
    queue<int> que;
    memset(dep,-1,sizeof(dep));
    dep[t] = 0;
    que.push(t);
    while(!que.empty())
    {
        int u = que.front();
        que.pop();
        if(u == s)
            return true;
        for(int i = head[u];~i;i = e[i].nxt)
        {
            int v = e[i].v;
            if(e[i ^ 1].flow && dep[v] == -1)
            {
                dep[v] = dep[u] + 1;
                //printf("%d %d\n",v,u);
                que.push(v);
            }
        }
    }
    return false;
}

int curedge[100050];

int dfs(int s,int t,int flow)
{
    if(s == t)
        return flow;
    int delta = flow;
    for(int i = head[s];~i;i = e[i].nxt)
    {
        int v = e[i].v;
        if(dep[v] == dep[s] - 1 && e[i].flow)
        {
            //printf("%d %d\n",s,v);
            int g = dfs(v,t,min((int)e[i].flow,delta));
            delta -= g;
            e[i].flow -= g;
            e[i ^ 1].flow += g;
            if(!delta)
                return flow;
        }
    }
    dep[s] = -1;
    return flow - delta;
}

int dinic()
{
    int ans = 0;
    while(bfs())
    {
        memcpy(curedge,head,sizeof(head));
        ans += dfs(s,t,0x3f3f3f3f);
    }
    return ans;
}

费用流 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
struct edge
{
    int v,nxt,flow,w;
}e[50000];

void adde(int u,int v,int flow,int w)
{
    e[ecnt].v = v;
    e[ecnt].nxt = head[u];
    e[ecnt].w = w;
    head[u] = ecnt;
    e[ecnt].flow = flow;
    ecnt++;
}

bool spfa()
{
    deque<int> que;
    memset(dep,0x3f3f3f3f,sizeof(dep));
    memset(inq,0,sizeof(inq));
    dep[t] = 0;
    que.push_back(t);
    while(!que.empty())
    {
        int u = que.front();
        que.pop_front();
        for(int i = head[u];~i;i = e[i].nxt)
        {
            int v = e[i].v;
            if(e[i ^ 1].flow && dep[u] - e[i].w < dep[v])
            {
                dep[v] = dep[u] + e[i ^ 1].w;
                if(!inq[v])
                {
                    if(que.empty() || dep[v] < dep[que.front()])
                        que.push_front(v);
                    else
                        que.push_back(v);
                    inq[v] = true;
                }
            }
        }
        inq[u] = false;
    }
    return dep[s] < 1061109567;
}

int dfs(int s,int t,int flow)
{
    if(s == t)
        return flow;
    int delta = flow;
    vis[s] = true;
    for(int i = head[s];~i;i = e[i].nxt)
    {
        int v = e[i].v;
        if(!vis[v] && dep[v] == dep[s] - e[i].w && e[i].flow)
        {
            //printf("%d %d\n",s,v);
            int g = dfs(v,t,min((int)e[i].flow,delta));
            delta -= g;
            ans += g * e[i].w;
            e[i].flow -= g;
            e[i ^ 1].flow += g;
            if(!delta)
                return flow;
        }
    }
    return flow - delta;
}

int dinic()
{
    int anss = 0;
    while(spfa())
    {
        vis[t] = 1;
        while(vis[t])
        {
            memset(vis,0,sizeof(vis));
            anss += dfs(s,t,0x3f3f3f3f);
        }
    }
    return anss;
}

最终结果为ans

无源汇上下界网络流(只有建图) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
memset(head,-1,sizeof(head));
memset(inv,0,sizeof(inv));
memset(ouv,0,sizeof(ouv));
ecnt = 0;
s = 0,t = 50050;
scanf("%lld%lld",&n,&m);
for(int i = 1;i <= m; ++ i)
{
    int fr,to,liml,limr;
    scanf("%d%d%d%d",&fr,&to,&liml,&limr);
    adde(fr,to,limr - liml,liml);
    adde(to,fr,0,liml);
    inv[to] += liml;
    ouv[fr] += liml;
}
int qsum = 0;
for(int i = 1;i <= n; ++ i)
{
    if(inv[i] > ouv[i])
        adde(s,i,inv[i] - ouv[i],0),adde(i,s,0,0),qsum += inv[i]-ouv[i];
    else
        adde(i,t,ouv[i]-inv[i],0),adde(t,i,0,0);
}
long long ans = 0;
if(dinic() == qsum) 有解;
else 无解;

有源汇上下界网络流 \(ss\) \(tt\)为源汇 \(s\) \(t\)为超级源点汇点 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for(int i = 0;i <= tt; ++ i)
{
    if(inf[i] > ouf[i])
        adde(s,i,inf[i]-ouf[i]),adde(i,s,0),sum += inf[i] - ouf[i];
    else
        adde(i,t,ouf[i]-inf[i]),adde(t,i,0);
}
int tot1 = dinic();
adde(tt,ss,0x3f3f3f3f);
adde(ss,tt,0);
int tot2 = dinic();
if(tot1 + tot2 == sum)
{
    printf("%d\n",e[ecnt - 1].flow);
}
else
    printf("impossible\n");