最大流之上下界可行流

1.无源汇上下界可行流
没有源点和汇点，边的容量下界为low(u,v)，上界为upp(u,v).求可行流.
我们只会求[0,c(u,v)]的最大流，一个直观的想法是所有边都减去下界。
但是这样是否能保证新图中满足容量限制和流量守恒么？
容量限制: 0<=f(u,v)-low(u,v)<=upp(u,v)-low(u,v)
流量限制: 会发现并不一定满足，因为每条边都减少low(u,v)，可能使得入的多或者出的多。我们可以用源点和汇点协调一下，如果入的流量少于出的流量，可以从源点向对应点连边；反之亦然。
这时我们发现只要求出新图中的最大流，如果他是满流的，就对应了原图中的一个可行流。(因为满流说明源点流出的流量都流满了，原图中每个点流量守恒，符合可行流的定义)

#include
using namespace std;
typedef long long ll;
const int N = 500;
const int M = 2*(10900+N);
const int INF = 1e9;
int q[N];
int d[N];
int h[N],e[M],ne[M],w[M],idx = 0;
int cur[N];
int l[M]; //减去下界后记得加上 
int n,m,k,T; int st,ed;
int in[N]; //减少的入的流量 
int out[N]; //减少的出的流量
ll tot = 0;
void add(int a,int b,int c)
{
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
bool bfs()
{
    int hh = 0,tt = 0;
    memset(d,-1,sizeof(d));
    d[st] = 0,cur[st] = h[st],q[tt++] = st;
    while(hh!=tt)
    {
        int u = q[hh++];
        for(int i=h[u];~i;i=ne[i])
        {
            int j = e[i];
            if(d[j]==-1&&w[i])
            {
                cur[j] = h[j];
                d[j] = d[u]+1;
                if(j==ed) return 1;
                q[tt++] = j;
            }
        }
    }
    return 0;
}
ll find(int u,ll limit)
{
    if(u==ed) return limit;
    ll flow = 0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        cur[u] = i;
        int j = e[i];
        if(d[j]==d[u]+1&&w[i])
        {
            ll t = find(j,min(1ll*w[i],limit-flow));
            if(!t) d[j] = -1;
            flow += t,w[i] -= t,w[i^1] += t;
        }
    }
    return flow;
}
ll dinic()
{
    ll ans = 0,flow;
    while(bfs()) while(flow = find(st,INF)) ans += flow;
    return ans;
}
void solve()
{
    memset(h,-1,sizeof(h));
    scanf("%d%d",&n,&m);
    st = 0,ed = n+1;
    for(int i=1;i<=m;++i)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        l[idx] = c;
        add(a,b,d-c);
        add(b,a,0);
        out[a] += c;
        in[b] += c;
    }
    for(int i=1;i<=n;++i)
    {
        int wh = abs(in[i]-out[i]);
        if(in[i]>out[i])
        {
            add(st,i,wh),add(i,st,0);
        }
        else if(in[i]<out[i])
        {
            add(i,ed,wh),add(ed,i,0);
        }
    }
    ll tot = 0;
    for(int i=h[st];~i;i=ne[i])
    {
        tot += w[i];    
    }   
    ll ans = dinic();
    if(ans != tot)
    {
        printf("NO");
    }
    else
    {
        printf("YES\n");
        for(int i=0;i<2*m;i+=2)
        {
            printf("%d\n",w[i^1]+l[i]); //对于可行流f，残留网络里的边权对应可行流的边的流量，原图中的边权对应容量-流量 
        }
    }
}
signed main(void)
{
    solve();
    return 0;
} 

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

2.有源汇上下界最大流
有源点和汇点、上下界。
可以按照无源汇的方法建图，此时除了源点和汇点都满足流量守恒，此时从汇点向源点连一条正无穷的边，则所有点满足流量守恒。若求可行流，问题就转化为无源汇的可行流。
但是我们要求比较高，求最大流。
一个直观的想法是求超级源点到超级汇点的最大流，之后再求原图中源点到汇点的最大流(因为求完第一个最大流之后可能还存在原图中源点到汇点的增广路)。其实这个想法不严谨，但是可以证明是正确的。因为求出超级源点到超级汇点的最大流(满流)之后，他们对应的边就算废了，因为都是满流，相当于没有。这个时候把正无穷的边删去，求得的原图中源点到原图中汇点的最大流满足可行流的定义(流量限制和容量限制)。

#include
using namespace std;
typedef long long ll;
const int N = 210;
const int M = 3*(10000+N);
const int INF = 2e9;
int q[N]; int d[N]; int cur[N];
int h[N],e[M],ne[M],w[M],idx = 0;
int in[N],out[N];
int st,ed,st2,ed2;
int n,m,k,T;
void add(int a,int b,int c)
{
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
bool bfs()
{
    int hh = 0,tt = 0;
    memset(d,-1,sizeof(d));
    d[st] = 0,cur[st] = h[st],q[tt++] = st;
    while(hh!=tt)
    {
        int u = q[hh++];
        for(int i=h[u];~i;i=ne[i])
        {
            int j = e[i];
            if(d[j]==-1&&w[i])
            {
                d[j] = d[u] + 1;
                cur[j] = h[j];
                if(j==ed) return true;
                q[tt++] = j;
            }
        }
    }
    return 0;
}
ll find(int u,ll limit)
{
    if(u==ed) return limit;
    ll flow = 0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        cur[u] = i;
        int j = e[i];
        if(d[j]==d[u]+1&&w[i])
        {
            ll t = find(j,min(1ll*w[i],limit-flow));
            if(!t) d[j] = -1;
            flow += t; w[i] -= t,w[i^1] += t;
        }
    }
    return flow;
}
ll dinic()
{
    ll ans = 0,flow;
    while(bfs()) while(flow = find(st,INF)) ans += flow;
    return ans;
}
void solve()
{
    memset(h,-1,sizeof(h));
    scanf("%d%d%d%d",&n,&m,&st2,&ed2);
    st = 0,ed = n+1;
    while(m--)
    {
        int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d);
        add(a,b,d-c);
        add(b,a,0);
        out[a]+=c;
        in[b]+=c;
    }
    for(int i=1;i<=n;++i)
    {
        int wh = abs(in[i]-out[i]);
        if(in[i]>out[i])
        {
            add(st,i,wh);
            add(i,st,0);
        }
        else if(in[i]<out[i])
        {
            add(i,ed,wh);
            add(ed,i,0);
        }
    }
    add(ed2,st2,INF); //流量为无穷的边，流量守恒 
    add(st2,ed2,0);
    ll tot = 0;
    for(int i=h[st];~i;i=ne[i]) tot += w[i]; 
    ll ans = dinic();
    if(ans < tot)
    {
        printf("No Solution");
    }
    else
    {
        int res = w[idx-1];
        w[idx-1] = w[idx-2] = 0;
        st = st2,ed = ed2;
        printf("%lld",dinic() + res);
    }
}
signed main(void)
{
    solve();
    return 0;
}
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

3.有源汇上下界最小流
基本思想同理最大流。先求出满流，保证是个可行流，然后再求原图中汇点到源点的最大流，反着流最大即正着流最小。

#include
using namespace std;
typedef long long ll;
const int N = 5e4+10;
const int M = 2*(125003+N);
const ll INF = 1e18;
int q[N]; int d[N]; int cur[N];
int h[N],e[M],ne[M];
ll w[M];
int idx = 0;
int in[N],out[N];
int st,ed,st2,ed2;
int n,m,k,T;
void add(int a,int b,ll c)
{
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
bool bfs()
{
    int hh = 0,tt = 0;
    memset(d,-1,sizeof(d));
    d[st] = 0,cur[st] = h[st],q[tt++] = st;
    while(hh!=tt)
    {
        int u = q[hh++];
        for(int i=h[u];~i;i=ne[i])
        {
            int j = e[i];
            if(d[j]==-1&&w[i])
            {
                d[j] = d[u] + 1;
                cur[j] = h[j];
                if(j==ed) return true;
                q[tt++] = j;
            }
        }
    }
    return 0;
}
ll find(int u,ll limit)
{
    if(u==ed) return limit;
    ll flow = 0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        cur[u] = i;
        int j = e[i];
        if(d[j]==d[u]+1&&w[i])
        {
            ll t = find(j,min(1ll*w[i],limit-flow));
            if(!t) d[j] = -1;
            flow += t; w[i] -= t,w[i^1] += t;
        }
    }
    return flow;
}
ll dinic()
{
    ll ans = 0,flow;
    while(bfs()) while(flow = find(st,INF)) ans += flow;
    return ans;
}
void solve()
{
    memset(h,-1,sizeof(h));
    scanf("%d%d%d%d",&n,&m,&st2,&ed2);
    st = 0,ed = n+1;
    while(m--)
    {
        int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d);
        add(a,b,d-c);
        add(b,a,0);
        out[a]+=c;
        in[b]+=c;
    }
    for(int i=1;i<=n;++i)
    {
        int wh = abs(in[i]-out[i]);
        if(in[i]>out[i])
        {
            add(st,i,wh);
            add(i,st,0);
        }
        else if(in[i]<out[i])
        {
            add(i,ed,wh);
            add(ed,i,0);
        }
    }
    add(ed2,st2,INF); //流量为无穷的边，流量守恒 
    add(st2,ed2,0); 
    ll tot = 0;
    for(int i=h[st];~i;i=ne[i]) tot += w[i]; 
    ll ans = dinic();
    if(ans < tot)
    {
        printf("No Solution");
    }
    else
    {
        int res = w[idx-1];
        w[idx-1] = w[idx-2] = 0;
        st = ed2,ed = st2;
        printf("%lld",res-dinic());
    }
}
signed main(void)
{
    solve();
    return 0;
}
/*
3 2 1 3
1 2 1000 2000
2 3 100 200
*/
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116