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

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

题目描述

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 76 1 0 21474836471 7 0 21474836476 2 0 21474836472 7 0 21474836476 3 0 21474836473 7 0 21474836476 4 0 21474836474 7 0 21474836476 5 0 21474836475 7 0 21474836475 1 1 21474836473 4 1 2147483647

样例输出

2

数据范围与提示

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

代码：

#include 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。