SGU 194 Reactor Cooling

SGU 194 Reactor Cooling

​​‎ 194. Reactor Cooling time limit per test: 0.5 sec. memory limit per test: 65536 KB input: standard output: standard

The terrorist group leaded by a well known international terrorist Ben Bladen is buliding a nuclear reactor to produce plutonium for the nuclear bomb they are planning to create. Being the wicked computer genius of this group, you are responsible for developing the cooling system for the reactor.

The cooling system of the reactor consists of the number of pipes that special cooling liquid flows by. Pipes are connected at special points, called nodes, each pipe has the starting node and the end point. The liquid must flow by the pipe from its start point to its end point and not in the opposite direction.

Let the nodes be numbered from 1 to N. The cooling system must be designed so that the liquid is circulating by the pipes and the amount of the liquid coming to each node (in the unit of time) is equal to the amount of liquid leaving the node. That is, if we designate the amount of liquid going by the pipe from i-th node to j-th as f ij, (put f ij = 0 if there is no pipe from node i to node j), for each i the following condition must hold:

sum(j=1..N, f ij) = sum(j=1..N, f ji)

Each pipe has some finite capacity, therefore for each i and j connected by the pipe must be f ij ≤ c ij where c ij is the capacity of the pipe. To provide sufficient cooling, the amount of the liquid flowing by the pipe going from i-th to j-th nodes must be at least l ij, thus it must be f ij ≥ l ij.

Given c ij and l ij for all pipes, find the amount f ij, satisfying the conditions specified above. Input The first line of the input file contains the number N (1 ≤ N ≤ 200) - the number of nodes and and M — the number of pipes. The following M lines contain four integer number each - i, j, l ij and c ij each. There is at most one pipe connecting any two nodes and 0 ≤ l ij ≤ c ij ≤ 10 5 for all pipes. No pipe connects a node to itself. If there is a pipe from i-th node to j-th, there is no pipe from j-th node to i-th. Output On the first line of the output file print YES if there is the way to carry out reactor cooling and NO if there is none. In the first case M integers must follow, k-th number being the amount of liquid flowing by the k-th pipe. Pipes are numbered as they are given in the input file. Sample test(s) Input

Test #1

4 6 1 2 1 2 2 3 1 2 3 4 1 2 4 1 1 2 1 3 1 2 4 2 1 2

Test #2

4 6 1 2 1 3 2 3 1 3 3 4 1 3 4 1 1 3 1 3 1 3 4 2 1 3

Output

Test #1

NO

Test #2

YES 1 2 3 2 1 1 sgu交题的时候要注意去掉多组数据 我们假设每个边都去给它流它的最小值 那么可能会产生一些点的入度和出度不守恒 那么怎么解决呢 我们考虑把他们的这些差值去和我假设的超级源 超级汇去建边 入度和<出度和的我们 向汇点建边 反之从源点向他这个点建边 然后我们每个点之间都把他们的自由流量建边 最后跑一遍最大流 看能否满足我的最大流等于所有源点的出边的和 然后最后输出答案的时候记得输出每条边的反边即可

update:现在再来看这题当初的理解是有些问题的再来补充一下 这个题 因为每个点的流入流出都是守恒的所以我们可以看出如果下界中流入的比流出的多 那么说明一会儿我平衡的时候需要更多的自由流来满足这个点的平衡所以这个自由流我就从源点再连过来 汇点同理

#include#include#include#include#define N 220#define inf 0x3f3f3f3fusing namespace std; inline char gc(){ static char now[1<<16],*T,*S; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while (ch<'0'||ch>'9') ch=gc(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x;}struct node{ int y,next,z;}data[N*N*2];int num=1,n,m,t,h[N],level[N],low[N*N],in[N],out[N],d[N];inline bool bfs(){ queueq;memset(level,0,sizeof(level));level[0]=1;q.push(0); while (!q.empty()){ int x=q.front();q.pop(); for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (level[y]||!z) continue;level[y]=level[x]+1;q.push(y);if (y==t) return 1; } }return 0;}int dfs(int x,int s){ if (x==t) return s;int ss=s; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (level[x]+1==level[y]&&z){ int xx=dfs(y,min(s,z));if (!xx) level[y]=0; s-=xx;data[i].z-=xx;data[i^1].z+=xx;if (!s) return ss; } }return ss-s;}inline void insert1(int x,int y,int z){ data[++num].y=y;data[num].z=z;data[num].next=h[x];h[x]=num; data[++num].y=x;data[num].z=0;data[num].next=h[y];h[y]=num;}int main(){ freopen("sgu194.in","r",stdin); int T=read(); while (T--){ n=read();m=read();num=1;memset(h,0,sizeof(h));memset(in,0,sizeof(in));memset(out,0,sizeof(out)); for (int i=1;i<=m;++i){ int x=read(),y=read(),c;low[i]=read();c=read(); data[++num].y=y;data[num].z=c-low[i];data[num].next=h[x];h[x]=num; data[++num].y=x;data[num].z=0;data[num].next=h[y];h[y]=num;out[x]+=low[i];in[y]+=low[i]; }t=n+1; for (int i=1;i<=n;++i) { d[i]=in[i]-out[i];if (d[i]<0) insert1(i,t,-d[i]);else insert1(0,i,d[i]); }int ans=0,tmp=0; while (bfs()) ans+=dfs(0,inf); for (int i=1;i<=n;++i) if (d[i]>0) tmp+=d[i]; if (tmp!=ans) printf("NO\n");else{ printf("YES\n"); for (int i=1;i<=m;++i) printf("%d\n",data[(i<<1)^1].z+low[i]); } } return 0;}

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