#117. 有源汇有上下界最小流

最新推荐文章于 2022-11-18 09:14:09 发布

闻道-问道

最新推荐文章于 2022-11-18 09:14:09 发布

阅读量244

点赞数

分类专栏：网络流

本文链接：https://blog.csdn.net/a1046765624/article/details/82941696

版权

网络流专栏收录该内容

14 篇文章

订阅专栏

本文详细介绍了如何解决最小流问题，通过构建一个网络流模型，并使用ISAP算法求解从源点到汇点的最小流。文章提供了完整的代码实现，包括网络流的初始化、边的添加、反向BFS以及ISAP算法的具体步骤。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目描述

n nn 个点，m mm 条边，每条边 e ee 有一个流量下界 lower(e) \text{lower}(e)lower(e) 和流量上界 upper(e) \text{upper}(e)upper(e)，给定源点 s ss 与汇点 t tt，求源点到汇点的最小流。

输入格式

第一行两个正整数 n nn、m mm、s ss、t tt。

之后的 m mm 行，每行四个整数 s ss、t tt、lower \text{lower}lower、upper \text{upper}upper。

输出格式

如果无解，输出一行 please go home to sleep。

否则输出最小流。

样例

样例输入

7 12 6 7
6 1 0 2147483647
1 7 0 2147483647
6 2 0 2147483647
2 7 0 2147483647
6 3 0 2147483647
3 7 0 2147483647
6 4 0 2147483647
4 7 0 2147483647
6 5 0 2147483647
5 7 0 2147483647
5 1 1 2147483647
3 4 1 2147483647

样例输出

数据范围与提示

1≤n≤50003,1≤m≤125003 1 \leq n \leq 50003 , 1\leq m \leq 1250031≤n≤50003,1≤m≤125003

代码：

#include <bits/stdc++.h>

using namespace std ;
#define copy( a , x ) memcpy ( a , x , sizeof a )
typedef long long LL ;

const int MAXN = 115000 ;
const int MAXE = 1000000 ;
const int MAXQ = 1000000 ;
const int INF = 0x3f3f3f3f ;

struct Edge {
    int v , n ;
    LL c ;
    Edge ( int var = 0 , LL cap = 0 , int next = 0 ) :
        v ( var ) , c ( cap ) , n ( next ) {}
} ;

struct netWork {
    Edge edge[MAXE] ;
    int adj[MAXN] , cntE ;
    int cur[MAXN] , d[MAXN] , num[MAXN] , pre[MAXN] ;
    bool vis[MAXN] ;
    int Q[MAXQ] , head , tail ;
    int s , t , nv ;
    LL flow ;

    void init () {
        cntE = 0 ;
        memset(adj,-1,sizeof(adj));
    }

    void addedge ( int u , int v , LL c , LL rc = 0 ) {
        edge[cntE] = Edge ( v ,  c , adj[u] ) ;
        adj[u] = cntE ++ ;
        edge[cntE] = Edge ( u , rc , adj[v] ) ;
        adj[v] = cntE ++ ;
    }

    void rev_Bfs () {
        memset(vis,0,sizeof(vis));
        memset(num,0,sizeof(num));
        d[t] = 0 ;
        vis[t] = 1 ;
        head = tail = 0 ;
        Q[tail ++] = t ;
        num[0] = 1 ;
        while ( head != tail ) {
            int u = Q[head ++] ;
            for ( int i = adj[u] ; ~i ; i = edge[i].n ) {
                int v = edge[i].v ;
                if ( vis[v] )
                    continue ;
                vis[v] = 1 ;
                d[v] = d[u] + 1 ;
                ++ num[d[v]] ;
                Q[tail ++] = v ;
            }
        }
    }

    LL ISAP () {
        copy ( cur , adj ) ;
        rev_Bfs () ;
        flow = 0 ;
        int i , u = pre[s] = s ;
        while ( d[s] < nv ) {
            if ( u == t ) {
                LL f = INF ;
                int pos ;
                for ( i = s ; i != t ; i = edge[cur[i]].v )
                    if ( f > edge[cur[i]].c )
                        f = edge[cur[i]].c , pos = i ;
                for ( i = s ; i != t ; i = edge[cur[i]].v )
                    edge[cur[i]].c -= f , edge[cur[i] ^ 1].c += f ;
                u = pos ;
                flow += f ;
            }
            for ( i = cur[u] ; ~i ; i = edge[i].n )
                if ( edge[i].c && d[u] == d[edge[i].v] + 1 )
                    break ;
            if ( ~i ) {
                cur[u] = i ;
                pre[edge[i].v] = u ;
                u = edge[i].v ;
            }
            else {
                if ( 0 == ( -- num[d[u]] ) )
                    break ;
                int mmin = nv ;
                for ( i = adj[u] ; ~i ; i = edge[i].n )
                    if ( edge[i].c && mmin > d[edge[i].v] )
                        cur[u] = i , mmin = d[edge[i].v] ;
                d[u] = mmin + 1 ;
                ++ num[d[u]] ;
                u = pre[u] ;
            }
        }
        return flow ;
    }
} ;
int read () {
	char c = ' ' ;
	int x = 0 ;
	while ( c < '0' || c > '9' )
		c = getchar () ;
	while ( c >= '0' && c <= '9' ) {
		x = x * 10 + c - '0' ;
		c = getchar () ;
	}
	return x ;
}
netWork net ;
int pp;
int n,m,k;
LL to[MAXN];
int ss,tt;
void work () {
    net.init () ;
    memset(to,0,sizeof(to));
    net.s = n+1, net.t = net.s+1, net.nv = net.t + 1 ;
    int u,v;
    int L,R;
	for(int i=1;i<=m;i++)
	{
	    //u=read();v=read();L=read();R=read();
	    scanf("%d%d%d%d",&u,&v,&L,&R);
	    net.addedge(u,v,R-L);
	    to[u]-=L;
	    to[v]+=L;
	}
	LL sum=0;
	for(int i=1;i<=n;i++)
	{
	    if(to[i]>0)
	    {
	        net.addedge(net.s,i,to[i]);
	        sum+=to[i];
	    }
	    else
	    {
	        net.addedge(i,net.t,-to[i]);
	    }
	}
	LL flow =net.ISAP();
	net.addedge(tt,ss,INF);
	flow += net.ISAP();
	if(flow==sum)
	{
	    printf ("%lld\n",net.edge[net.cntE-1].c);
	    return;
	}
	puts("please go home to sleep");

}

int main()
{
    //n=read();m=read();ss=read();tt=read();
    scanf("%d%d%d%d",&n,&m,&ss,&tt);
    work();
    return 0;
}