Flow construction SGU - 176 有源汇有上下界最小流 二分法和回流法

时间：2023-03-08 21:31:33
/**

题目：Flow construction SGU - 176

链接：https://vjudge.net/problem/SGU-176

题意：

有源汇有上下界的最小流。

给定n个点，m个管道。每个管道给出u,v,z,c。u表示起点，v表示终点，z表示容量，如果c==1,那么表示还有下界为z。

如果c==0,表示没有下界。

求从1到n的最小流。

思路：

第一种做法：

转化为无源汇求超级源S到超级汇T的最大流flow1(此时从s出发的流和为flow1),然后讲t到s的边删掉（可以使流量等于容量，这样求t到s的最大流就不会经过他了。）

求t到s的最大流flow2(从s出发的流减少的量).是为了回流，因为原先求flow1的过程，是为了满足下界的可行流。这个在原图的可行流可能可以变得更小，通过回流使其缩小。

求t到s的最大流并不会影响原来附加边的流量。所以保证了是下界满足的可行流。

然后用flow1-flow2就是结果。

第二种做法：

构造无源汇有上下界的可行流做法，只不过t到s的边的上下界要改一下。

二分t到s的上界a，下界为0，如果是可行流最小的a便是最小流。如果是求最大流，那么就是二分t到s的下界a，上界无穷，如果是可行流，那么最大的a便是最大流。

不懂的看文档解释。https://wenku.baidu.com/view/0f3b691c59eef8c75fbfb35c.html

关于每次二分，处理一次最大流，那么下次在计算最大流的时候，难道又要重新建图？

反正是结构体存的，新加一个变量存储。下次直接从这个变量获取即可。注意t到s这条边的修改。或者最后面再加进去。

*/

第一种做法

#include<iostream>

#include<cstring>

#include<vector>

#include<map>

#include<cstdio>

#include<algorithm>

#include<queue>

using namespace std;

const int INF = 0x3f3f3f3f;

typedef long long LL;

const int N = ;///n+m=1365

int in[N];

int out[N];

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;

    vector<int> G[N];

    bool vis[N];

    int d[N];

    int cur[N];

    void init(int n)

    {

        this->n = n;

        for(int i = ; i <= n; i++) G[i].clear();

        edges.clear();

    }

    void AddEdge(int from,int to,int cap)

    {

        edges.push_back(Edge(from,to,cap,));

        edges.push_back(Edge(to,from,,));

        m = edges.size();

        G[from].push_back(m-);

        G[to].push_back(m-);

    }

    bool BFS()

    {

        memset(vis, , sizeof vis);

        queue<int> Q;

        Q.push(s);

        d[s] = ;

        vis[s] = ;

        while(!Q.empty())

        {

            int x = Q.front();

            Q.pop();

            for(int i = ; i < G[x].size(); i++)

            {

                Edge &e = edges[G[x][i]];

                if(!vis[e.to]&&e.cap>e.flow)

                {

                    vis[e.to] = ;

                    d[e.to] = d[x]+;

                    Q.push(e.to);

                }

            }

        }

        return vis[t];

    }

    int DFS(int x,int a)

    {

        if(x==t||a==) return a;

        int flow = , f;

        for(int &i = cur[x]; i < G[x].size(); i++)

        {

            Edge& e = edges[G[x][i]];

            if(d[x]+==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>)

            {

                e.flow += f;

                edges[G[x][i]^].flow -= f;

                flow += f;

                a -= f;

                if(a==) break;

            }

        }

        return flow;

    }

    int Maxflow(int s,int t)

    {

        this->s = s, this->t = t;

        int flow = ;

        while(BFS())

        {

            memset(cur, , sizeof cur);

            flow += DFS(s,INF);

        }

        return flow;

    }

};

int dw[N*N];

int main()

{

    int n, m;

    while(scanf("%d%d",&n,&m)==)

    {

        Dinic dinic;

        dinic.init(n+);

        int u, v, cap, flag;///1,n为普通源汇。

        int s = , t = n+;///超级源汇。

        memset(dw, , sizeof dw);

        memset(in, , sizeof in);

        memset(out, , sizeof out);

        for(int i = ; i<m; i++){

            scanf("%d%d%d%d",&u,&v,&cap,&flag);

            if(flag==){

                dw[i] = cap;

                dinic.AddEdge(u,v,);

                out[u]+=cap;

                in[v]+=cap;

            }else

            {

                dinic.AddEdge(u,v,cap);

            }

        }

        int ts;

        dinic.AddEdge(n,,INF);

        ts = dinic.edges.size()-;

        int sum = ;

        for(int i = ; i <= n; i++){

            if(in[i]>out[i]){

                dinic.AddEdge(s,i,in[i]-out[i]);

                sum += in[i]-out[i];

            }

            if(in[i]<out[i]){

                dinic.AddEdge(i,t,out[i]-in[i]);

            }

        }

        int flow = dinic.Maxflow(s,t);

        if(flow!=sum){

            printf("Impossible\n"); continue;

        }

        dinic.edges[ts].cap = dinic.edges[ts].flow;///使其求n到1的最大流无法经过。

        int flow2 = dinic.Maxflow(n,);///回流

        printf("%d\n",flow-flow2);

        for(int i = ; i < m; i++){

            if(i==m-){

                printf("%d\n",dinic.edges[*i].flow+dw[i]);

            }else

            {

                printf("%d ",dinic.edges[*i].flow+dw[i]);

            }

        }

    }

    return ;

}

第二种做法

#include<iostream>

#include<cstring>

#include<vector>

#include<map>

#include<cstdio>

#include<algorithm>

#include<queue>

using namespace std;

const int INF = 0x3f3f3f3f;

typedef long long LL;

const int N = ;///n+m=1365

int in[N];

int out[N];

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;

    vector<int> G[N];

    bool vis[N];

    int d[N];

    int cur[N];

    void init(int n)

    {

        this->n = n;

        for(int i = ; i <= n; i++) G[i].clear();

        edges.clear();

    }

    void AddEdge(int from,int to,int cap)

    {

        edges.push_back(Edge(from,to,cap,));

        edges.push_back(Edge(to,from,,));

        m = edges.size();

        G[from].push_back(m-);

        G[to].push_back(m-);

    }

    bool BFS()

    {

        memset(vis, , sizeof vis);

        queue<int> Q;

        Q.push(s);

        d[s] = ;

        vis[s] = ;

        while(!Q.empty())

        {

            int x = Q.front();

            Q.pop();

            for(int i = ; i < G[x].size(); i++)

            {

                Edge &e = edges[G[x][i]];

                if(!vis[e.to]&&e.cap>e.flow)

                {

                    vis[e.to] = ;

                    d[e.to] = d[x]+;

                    Q.push(e.to);

                }

            }

        }

        return vis[t];

    }

    int DFS(int x,int a)

    {

        if(x==t||a==) return a;

        int flow = , f;

        for(int &i = cur[x]; i < G[x].size(); i++)

        {

            Edge& e = edges[G[x][i]];

            if(d[x]+==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>)

            {

                e.flow += f;

                edges[G[x][i]^].flow -= f;

                flow += f;

                a -= f;

                if(a==) break;

            }

        }

        return flow;

    }

    int Maxflow(int s,int t)

    {

        this->s = s, this->t = t;

        int flow = ;

        while(BFS())

        {

            memset(cur, , sizeof cur);

            flow += DFS(s,INF);

        }

        return flow;

    }

};

int dw[N*N];

int main()

{

    int n, m;

    while(scanf("%d%d",&n,&m)==)

    {

        Dinic dinic;

        dinic.init(n+);

        int u, v, cap, flag;///1,n为普通源汇。

        int s = , t = n+;///超级源汇。

        memset(dw, , sizeof dw);

        memset(in, , sizeof in);

        memset(out, , sizeof out);

        for(int i = ; i<m; i++){

            scanf("%d%d%d%d",&u,&v,&cap,&flag);

            if(flag==){

                dw[i] = cap;

                dinic.AddEdge(u,v,);

                out[u]+=cap;

                in[v]+=cap;

            }else

            {

                dinic.AddEdge(u,v,cap);

            }

        }

        int sum = ;

        for(int i = ; i <= n; i++){

            if(in[i]>out[i]){

                dinic.AddEdge(s,i,in[i]-out[i]);

                sum += in[i]-out[i];

            }

            if(in[i]<out[i]){

                dinic.AddEdge(i,t,out[i]-in[i]);

            }

        }

        Dinic Tdinic = dinic;

        int flow;

        int lo = , hi = INF, mid;

        while(lo<hi){///最小流，二分上界，取最小值。

            mid = (lo+hi)/;

            dinic = Tdinic;

            dinic.AddEdge(n,,mid);

            flow = dinic.Maxflow(s,t);

            if(flow!=sum){

                lo = mid+;

            }else

            {

                hi = mid;

            }

        }

        if(hi==lo){

            printf("Impossible\n"); continue;

        }

        printf("%d\n",hi);

        dinic = Tdinic;///注意复原，因为此时的dinic不是最小流为hi的时候的。要重新计算。

        dinic.AddEdge(n,,hi);

        dinic.Maxflow(s,t);

        for(int i = ; i < m; i++){

            if(i==m-){

                printf("%d\n",dinic.edges[*i].flow+dw[i]);

            }else

            {

                printf("%d ",dinic.edges[*i].flow+dw[i]);

            }

        }

    }

    return ;

}

相关文章