SGU 176 Flow construction 有源汇有上下界的最小流

题意就是给出一个图。有源汇

然后每条边都有容量的上下界限制。

问的是是否有一个最小流，使得每条边得流量都满足流量限制，并且流量守恒

我使用的是二分的方法。

每次二分都要重新构图，然后计算。

构图的方法是按照论文中所说。

设原来的源汇为s, t，附加源汇为S, T

对于一个点i，计算流入该点的下界总和减去流出该点的下界总和为M[i].

如果M[i]是正数，添加边(S,i)，容量为M[i]

否则添加边(i, T) 容量为-M[i]

然后对于每条边，设上下届分为up和down，起点终点为u,v

那么添加边(u, v)流量为up - down即可

由于我们要二分一个流量然后判断可行。

假设二分的流量是x,则添加边(t, s) 流量为x

然后求最大流看是否使得源s连出去的边都满流。若都满流即为可行流。

最后求得的最小的该x即为最终原图中的最小流

输出边时则输出边得流量加上原来的down。因为我们之前减掉了。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define MAXN 111
#define MAXM 21111
#define eps 1e-8
#define INF 1000000009
using namespace std;
struct EDGE
{
    int v, next;
    int w;
} edge[MAXM];
int head[MAXN], e;
inline void init()
{
    memset(head, -1, sizeof(head));
    e = 0;
}
inline void add(int u, int v, int w)
{
    edge[e].v = v;
    edge[e].w = w;
    edge[e].next = head[u];
    head[u] = e++;
    edge[e].v = u;
    edge[e].w = 0;
    edge[e].next = head[v];
    head[v] = e++;
}
int n;
int h[MAXN];
int gap[MAXN];
int src, des;
inline int dfs(int pos, int cost)
{
    if (pos == des) return cost;
    int j, minh = n - 1;
    int lv = cost, d;
    for (j = head[pos]; j != -1; j = edge[j].next)
    {
        int v = edge[j].v;
        int w = edge[j].w;
        if(w > 0)
        {
            if (h[v] + 1 == h[pos])
            {
                if (lv < edge[j].w) d = lv;
                else d = edge[j].w;
                d = dfs(v, d);
                edge[j].w -= d;
                edge[j ^ 1].w += d;
                lv -= d;
                if (h[src] >= n) return cost - lv;
                if (lv == 0) break;
            }
            if (h[v] < minh) minh = h[v];
        }
    }
    if (lv == cost)
    {
        --gap[h[pos]];
        if (gap[h[pos]] == 0) h[src] = n;
        h[pos] = minh + 1;
        ++gap[h[pos]];
    }
    return cost - lv;
}
int sap()
{
    int ret = 0;
    memset(gap, 0, sizeof(gap));
    memset(h, 0, sizeof(h));
    gap[0] = n;
    while (h[src] < n) ret += dfs(src, INF);
    return ret;
}
int nt, m;
int xj[MAXN];
int uu[MAXM], vv[MAXM], low[MAXM], z[MAXM];
int id[MAXN][MAXN], eid, total, limit;
void build(int x)
{
    init();
    for(int i = 0; i < m; i++)
    {
        id[uu[i]][vv[i]] = e;
        add(uu[i], vv[i], z[i] - low[i]);
    }
    for(int i = 1; i <= nt; i++)
    {
        if(xj[i] > 0) add(src, i, xj[i]);
        else add(i, des, -xj[i]);
    }
    add(nt, 1, x);
}
void gao()
{
    int l = 0, r = limit, mid;
    while(l <= r)
    {
        mid = (l + r) >> 1;
        build(mid);
        if(sap() == total) r = mid - 1;
        else l = mid + 1;
    }
    build(l);
    sap();

    printf("%d\n", l);
    for(int i = 0; i < m; i++)
    {
        int tmp = id[uu[i]][vv[i]];
        printf("%d ", edge[tmp ^ 1].w + low[i]);
    }
    printf("\n");
}
int main()
{
    while(scanf("%d%d", &nt, &m) != EOF)
    {
        init();
        total = 0; limit = 0;
        memset(xj, 0, sizeof(xj));
        for(int i = 0; i < m; i++)
        {
            scanf("%d%d%d%d", &uu[i], &vv[i], &z[i], &low[i]);
            if(low[i] == 1) low[i] = z[i];
            xj[vv[i]] += low[i];
            xj[uu[i]] -= low[i];
            if(uu[i] == 1) limit += z[i];
        }
        src = nt + 1;
        des = nt + 2;
        n = des;
        for(int i = 1; i <= nt; i++)
            if(xj[i] > 0) total += xj[i];
        build(INF);
        if(sap() != total) printf("Impossible\n");
        else gao();
    }
    return 0;
}

相关阅读:
Linux下编译main.c文件,命令中的gcc -o -c是什么意思
k8s-NFS系统配置
【realme x2手机解锁BootLoader（简称BL）】
【Spring Boot】事务和事务传播机制
019 Linux tcpdump 抓包案例入门可真简单啊？
6.filters滤波
算法提高-AC自动机
Nginx 基础
【资料上新】基于3568开发板的NPU开发资料全面升级
使用VM Ware创建虚拟机

原文地址：https://blog.csdn.net/weixin_71792169/article/details/127856901

SGU 176 Flow construction 有源汇 有上下界的最小流

SGU 176 Flow construction 有源汇有上下界的最小流