SGU194 无源无汇有容量上下界的可行流

Posted on | In , ,

建图方法：
令每条边的容量下界为0，此刻容量上界变成了$up-down$（上界减去下届），我们定义一个$du[]$数组保存每个节点的入流之和与出流之和的差，建一个超级源点和一个超级汇点，当$du[i]>0$，说明入流大于出流，为了满足流量守恒，连一条$st$到$i$容量为$du[i]$的边，当$du[i]<0$,说明出流大于入流，连一条$i$到$sd$容量为$-du[i]$的边。
最构造的网络进行一次最大流，当且仅当所有附加弧满载时原网络有可行流，否则没有。

题目链接

题解

建图方法：
令每条边的容量下界为0，此刻容量上界变成了$up-down$（上界减去下届），我们定义一个$du[]$数组保存每个节点的入流之和与出流之和的差，建一个超级源点和一个超级汇点，当$du[i]>0$，说明入流大于出流，为了满足流量守恒，连一条$st$到$i$容量为$du[i]$的边，当$du[i]<0$,说明出流大于入流，连一条$i$到$sd$容量为$-du[i]$的边。
最构造的网络进行一次最大流，当且仅当所有附加弧满载时原网络有可行流，否则没有

代码

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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
// Dinic(最大流算法)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=1e9;

const int maxn = 160020;

int n, m, u, v, s , t, below, up;
int sum;

struct Edge
{
    int from, to, cap, flow;
    Edge(int u,int v,int c,int f):from(u), to(v), cap(c), flow(f) {}
};

struct Dinic
{
    int n, m, s, t;       // 节点数,边数(包括反向弧),源点编号和汇点编号
    vector<Edge> edges;   // 边数。edges[e]和edges[e^1]互为反向弧
    vector<int> G[maxn];  // 邻接表，G[i][j]表示节点i的第j条边在e数组的序号
    bool vis[maxn];       // BFS使用
    int d[maxn];          // 从起点到i的距离
    int cur[maxn];        // 当前弧下标

    void init()
    {
        for(int i=0; i<=n+3; i++)
            G[i].clear();
        edges.clear();
    }

    void Addedge(int from, int to, int cap)
    {
        edges.push_back(Edge(from, to, cap, 0));
        edges.push_back(Edge(to, from, 0, 0));
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool BFS()
    {
        memset(vis,0,sizeof(vis));
        queue<int>Q;
        Q.push(s);
        d[s]=0;
        vis[s]=1;
        while(!Q.empty())
        {
            int x=Q.front();
            Q.pop();
            for(int i=0; i<G[x].size(); i++)
            {
                Edge& e=edges[G[x][i]];
                if(!vis[e.to] && e.cap>e.flow) //只考虑残量网络中的弧
                {
                    vis[e.to]=1;
                    d[e.to]=d[x]+1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    int DFS(int x,int a)
    {
        if(x==t || a==0) return a;
        int flow=0, f;
        for(int& i=cur[x]; i<G[x].size(); i++) // 从上次考虑的弧
        {
            Edge& e=edges[G[x][i]];
            if(d[x]+1 == d[e.to] && (f=DFS(e.to, min(a, e.cap-e.flow)))>0)
            {
                e.flow+=f;
                edges[G[x][i]^1].flow-=f;
                flow+=f;
                a-=f;
                if(a==0) break;
            }
        }
        return flow;
    }

    int Maxflow(int s,int t)
    {
        this->s=s; this->t=t;
        int flow=0;
        while(BFS())
        {
            memset(cur, 0, sizeof(cur));
            flow += DFS(s,INF);
        }
        return flow;
    }
};

int kx[maxn], d[maxn];

int main()
{
    Dinic now;
    scanf("%d%d", &n, &m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d%d", &u,  &v, &below, &up);
        now.Addedge(u, v, up-below);
        kx[i]=below;
        d[u]-=below;
        d[v]+=below;
    }
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        if(d[i]>0){
            now.Addedge(0, i, d[i]);
            sum+=d[i];
        }
        if(d[i]<0) now.Addedge(i, n+1, -d[i]);
    }
    int ans = now.Maxflow(0,n+1);
    if(ans != sum) puts("NO");
    else
    {
        puts("YES");
        for(int i=1;i<=m;i++)
            printf("%d\n", now.edges[2*(i-1)].flow+kx[i]);
    }
    return 0;
}