有汇源上下界最大流和最小流

有汇源上下界最大流
有源汇上下界最大流最小流理解
题目
理解

#include
using namespace std;
const int N=610,M=3e4,INF=0x3f3f3f3f;
int n,m,S,T;
int s,t;
int d[N];
int q[N],cur[N],h[N],ne[M],e[M],f[M],idx,A[N];


void add(int a,int b,int c,int d)
{
    e[idx]=b,ne[idx]=h[a],f[idx]=d-c,h[a]=idx++;
    e[idx]=a,ne[idx]=h[b],f[idx]=0,h[b]=idx++;
}

bool bfs()
{
    memset(d,-1,sizeof(d));
    int hh=0,tt=0;
    q[hh]=S,cur[S]=h[S],d[S]=0;
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i])
        {
            int ver=e[i];
            if(d[ver]==-1&&f[i])
            {
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T) return true;
                q[++tt]=ver;
            }
        }
    }
    return false;
}

int find(int u,int limit)
{
    if(u==T) return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        cur[u]=i;
        int ver=e[i];
        if(d[ver]==d[u]+1&&f[i])
        {
            int t=find(ver,min(f[i],limit-flow));
            if(!t) d[ver]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}



int dinic()
{
    int r=0;
    int flow;
    while(bfs()) while(flow=find(S,INF)) r+=flow;
    return r;
}



int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    S=0,T=n+1;
    memset(h,-1,sizeof(h));
    int tot=0;
    for(int i=1;i<=m;i++)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        add(a,b,c,d);
        A[a]-=c,A[b]+=c;
    }
    
    for(int i=1;i<=n;i++)
    {
        if(A[i]>0) add(S,i,0,A[i]),tot+=A[i];
        else if(A[i]<0) add(i,T,0,-A[i]);
    }
    add(t,s,0,INF);
    if(dinic()<tot)
    {
        puts("No Solution");
    }else
    {
        int res=f[idx-1];
        S=s,T=t;
        f[idx-1]=f[idx-2]=0;
        printf("%d\n",res+dinic());
    }
    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

有汇源上下界最小流
题目

#include
using namespace std;
const int N=1e6+10,M=5e6+10,INF=0x3f3f3f3f;
int n,m,S,T;
int s,t;
int d[N];
int q[N],cur[N],h[N],ne[M],e[M],f[M],idx,A[N];


void add(int a,int b,int c,int d)
{
    e[idx]=b,ne[idx]=h[a],f[idx]=d-c,h[a]=idx++;
    e[idx]=a,ne[idx]=h[b],f[idx]=0,h[b]=idx++;
}

bool bfs()
{
    memset(d,-1,sizeof(d));
    int hh=0,tt=0;
    q[hh]=S,cur[S]=h[S],d[S]=0;
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i])
        {
            int ver=e[i];
            if(d[ver]==-1&&f[i])
            {
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T) return true;
                q[++tt]=ver;
            }
        }
    }
    return false;
}

int find(int u,int limit)
{
    if(u==T) return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        cur[u]=i;
        int ver=e[i];
        if(d[ver]==d[u]+1&&f[i])
        {
            int t=find(ver,min(f[i],limit-flow));
            if(!t) d[ver]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}



int dinic()
{
    int r=0;
    int flow;
    while(bfs()) while(flow=find(S,INF)) r+=flow;
    return r;
}



int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    S=0,T=n+1;
    memset(h,-1,sizeof(h));
    int tot=0;
    for(int i=1;i<=m;i++)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        add(a,b,c,d);
        A[a]-=c,A[b]+=c;
    }
    
    for(int i=1;i<=n;i++)
    {
        if(A[i]>0) add(S,i,0,A[i]),tot+=A[i];
        else if(A[i]<0) add(i,T,0,-A[i]);
    }
    add(t,s,0,INF);
    if(dinic()<tot)
    {
        puts("No Solution");
    }else
    {
        int res=f[idx-1];
        S=t,T=s;
        f[idx-1]=f[idx-2]=0;
        printf("%d\n",res-dinic());
    }
    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