「zoj2314」Reactor Cooling (无源汇上下界可行流)

时间:2022-09-08 20:53:32

题意:

   给n个点,及m根pipe,每根pipe用来流躺液体的,单向的,每时每刻每根pipe流进来的物质要等于流出去的物质,要使得m条pipe组成一个循环体,里面流躺物质。

并且满足每根pipe一定的流量限制,范围为[Li,Ri].即要满足每时刻流进来的不能超过Ri(最大流问题),同时最小不能低于Li。

题解:

上界用ci表示,下界用bi表示。

下界是必须流满的,那么对于每一条边,去掉下界后,其*流为ci– bi。

主要思想:每一个点流进来的流=流出去的流

对于每一个点i,令

Mi= sum(i点所有流进来的下界流)– sum(i点所有流出去的下界流)

如果Mi大于0,代表此点必须还要流出去Mi的*流,那么我们从源点连一条Mi的边到该点。

如果Mi小于0,代表此点必须还要流进来Mi的*流,那么我们从该点连一条Mi的边到汇点。

如果求S->T的最大流,看是否满流(S的相邻边都流满)。

满流则有解,否则无解。

 

CODE:

 1 #include<iostream>  2 #include<cstdio>  3 #include<cstring>  4 #define inf 0x7fffffff  5 #define T 201  6 using namespace std;  7 inline int read()  8 {  9 int x=0,f=1;char ch=getchar(); 10 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 11 while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();} 12 return x*f; 13 } 14 int n,m,cnt; 15 int head[205],cur[205],h[205],q[205],in[205]; 16 int low[100005]; 17 struct data{int to,next,v;}e[100005]; 18 void ins(int u,int v,int w) 19 {e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].v=w;} 20 void insert(int u,int v,int w) 21 {ins(u,v,w);ins(v,u,0);} 22 bool bfs() 23 { 24 for(int i=1;i<=T;i++)h[i]=-1; 25 int t=0,w=1;q[0]=0;h[0]=0; 26 while(t!=w) 27  { 28 int now=q[t];t++; 29 for(int i=head[now];i;i=e[i].next) 30 if(e[i].v&&h[e[i].to]==-1) 31  { 32 h[e[i].to]=h[now]+1; 33 q[w++]=e[i].to; 34  } 35  } 36 if(h[T]==-1)return 0; 37 return 1; 38 } 39 int dfs(int x,int f) 40 { 41 if(x==T)return f; 42 int w,used=0; 43 for(int i=cur[x];i;i=e[i].next) 44 if(h[e[i].to]==h[x]+1) 45  { 46 w=f-used;w=dfs(e[i].to,min(e[i].v,w)); 47 e[i].v-=w;if(e[i].v)cur[x]=i;e[i^1].v+=w; 48 used+=w;if(used==f)return f; 49  } 50 if(!used)h[x]=1; 51 return used; 52 } 53 void dinic() 54 {while(bfs()){for(int i=0;i<=T;i++)cur[i]=head[i];dfs(0,inf);}} 55 void build() 56 { 57 for(int i=1;i<=n;i++) 58 if(in[i]>0)insert(0,i,in[i]); 59 else insert(i,T,-in[i]); 60 } 61 bool jud() 62 { 63 for(int i=head[0];i;i=e[i].next) 64 if(e[i].v)return 0; 65 return 1; 66 } 67 int main() 68 { 69 int test=read(); 70 while(test--) 71  { 72 cnt=1; 73 memset(head,0,sizeof(head)); 74 memset(in,0,sizeof(in)); 75 n=read();m=read(); 76 for(int i=1;i<=m;i++) 77  { 78 int u,v,w; 79 u=read();v=read();low[i]=read();w=read(); 80 in[u]-=low[i];in[v]+=low[i]; 81 insert(u,v,w-low[i]); 82  } 83  build(); 84  dinic(); 85 if(!jud())printf("NO\n"); 86 else 87  { 88 printf("YES\n"); 89 for(int i=1;i<=m;i++) 90 printf("%d\n",e[(i<<1)^1].v+low[i]); 91  } 92 puts(""); 93  } 94 return 0; 95 }