精华内容
下载资源
问答
  •  有源汇的可行流:转换成无源汇的可行流来做,即从t→s连一条容量为正无穷  下限的边,整个图就转化成了循环图  有源汇的最大流/有源汇的最小流:拆边的方法太奇怪不好理解  二分t→s的下限即可   ...

    Reactor Cooling

     

    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 fij, (put fij= 0 if there is no pipe from node i to node j), for each i the following condition must hold:

    fi,1+fi,2+...+fi,N = f1,i+f2,i+...+fN,i

    Each pipe has some finite capacity, therefore for each i and j connected by the pipe must be fij <= cij where cij 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 lij, thus it must be fij >= lij.

    Given cij and lij for all pipes, find the amount fij, satisfying the conditions specified above.

     

    This problem contains multiple test cases!

    The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

    The output format consists of N output blocks. There is a blank line between output blocks.

     

    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, lij and cij each. There is at most one pipe connecting any two nodes and 0 <= lij <= cij <= 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.

     

      第一次在浙大的OJ上做题w

      题意大概就是给定一张管道网络以及每一根管道流量的上界和下界

      判断是否存在可行流,以及如果存在的话输出一组可行流

     

      感谢NewFarking的文章 (戳这里

      做法还是理解了一会儿的呢..

     

      对于一根管道(u,v),设其流量限制为[l,r]

      为了简便地解决这个问题我们有一个初步的想法

      就是先强制流掉下限流量,然后剩下的给出流量限制之后再随意流

      

      实际上代码也基本是这样实现的

      先从u到v连一条容量为r-l的边,也就是自由流

      看起来我们将这根管道的下限流确实是流掉了呢

      但是整张网络并没有

      比如这张图

      w到u必须流掉的10单位流量,但从u出发只强制流掉了5单位的流量

      还有5单位的流量必须流出去

      用什么来强制流出去呢?

      答案是从s到u建一条容量为5的边

      因为我们最终判断是否存在可行流的条件是s连出的边是否全部满流

      那么一旦存在可行解,这5个单位的流量全流出去了,能达到我们的目的

      这道题让我们输出一组可行解,我是在Dfs的过程中处理的

     

     


      

      UPD.顺便写一写其他几种的建图方法:

      有源汇的可行流:转换成无源汇的可行流来做,即从t→s连一条容量为正无穷

      无下限的边,整个图就转化成了循环图

      有源汇的最大流/有源汇的最小流:拆边的方法太奇怪不好理解

      二分t→s的下限即可

     

     

    program zoj2314;
    const maxn = 210;maxm = 80010;
    var fa,next,ter,w,rec,flow:array[-1..maxm]of longint;
        link,dis,opt,inp:array[-1..maxn]of longint;
        vis:array[-1..maxn]of boolean;
        n,m,e,tt,test,i,s,t,x,y,l,r:longint;
    
    function min(a,b:longint):longint;
    begin
            if a<b then exit(a) else exit(b);
    end;
    
    function spfa:boolean;
    var head,tail,x,j:longint;
    begin
        fillchar(vis,sizeof(vis),true);
        fillchar(dis,sizeof(dis),63);
        head:=0;tail:=1;opt[1]:=s;vis[s]:=false;dis[s]:=0;
        while head<>tail do
        begin
            head:=(head+1) mod maxn;
            x:=opt[head];j:=link[x];
            while j<>0 do
            begin
                if (dis[x]+1<dis[ter[j]])and(w[j]>0) then
                begin
                    dis[ter[j]]:=dis[x]+1;
                    if vis[ter[j]] then
                    begin
                        vis[ter[j]]:=false;
                        tail:=(tail+1) mod maxn;
                        opt[tail]:=ter[j];
                    end;
                end;
                j:=next[j];
            end;
            vis[x]:=true;
        end;
        if dis[t]<>dis[t+1] then exit(true) else exit(false);
    end;
    
    function dfs(p,sum:longint):longint;
    var tem,j,x:longint;
    begin
        tem:=0;
        if p=t then exit(sum);
        j:=link[p];
        while j<>0 do
         begin
            if (dis[ter[j]]=dis[p]+1)and(w[j]>0) then
            begin
                x:=dfs(ter[j],min(sum-tem,w[j]));
                inc(tem,x);dec(w[j],x);inc(w[rec[j]],x);
                           // writeln(p,' ',ter[j],' ',fa[j],' ',x);
                if rec[j]=j+1 then inc(flow[fa[j]],x) else dec(flow[fa[rec[j]]],x);
                if tem=sum then exit(sum);
            end;
            j:=next[j];
        end;
        exit(tem);
    end;
    
    procedure add(x,y,z,fat:longint);
    begin
           // writeln(x,' ',y,' ',z);
        inc(e);ter[e]:=y;next[e]:=link[x];link[x]:=e;w[e]:=z;fa[e]:=fat;rec[e]:=e+1;
        inc(e);ter[e]:=x;next[e]:=link[y];link[y]:=e;w[e]:=0;fa[e]:=fat;rec[e]:=e-1;
    end;
    
    function Jud:boolean;
    var j:longint;
    begin
        j:=link[s];
        while j<>0 do
        begin
            if w[j]>0 then exit(false);
            j:=next[j];
        end;
        exit(true);
    end;
    
    procedure Solve;
    var i,sum:longint;
    begin
            sum:=0;
        while spfa do inc(sum,dfs(s,1000000007));
        if not Jud then writeln('NO') else
        begin
            writeln('YES');
            for i:=1 to m do writeln(flow[i]);
        end;
        writeln;
    end;
    
    begin
        //assign(input,'zoj2314.in');reset(input);
        readln(test);
        for tt:=1 to test do
        begin
            readln;
            readln(n,m);
            fillchar(inp,sizeof(inp),0);
            fillchar(link,sizeof(link),0);
            fillchar(next,sizeof(next),0);
            e:=0;s:=0;t:=n+1;
            for i:=1 to m do
            begin
                readln(x,y,l,r);
                            flow[i]:=l;
                dec(inp[x],l);inc(inp[y],l);
                add(x,y,r-l,i);
            end;
            for i:=1 to n do if inp[i]>0 then add(s,i,inp[i],0) else
                if inp[i]<0 then add(i,t,-inp[i],0);
            Solve;
        end;
    end.

     

    转载于:https://www.cnblogs.com/mjy0724/p/4465832.html

    展开全文
  • 无源汇上下界可行流

    2018-02-28 14:49:04
    无源汇上下界可行流:没有源汇的上下界网络流。因为只需要满足每个点流量守恒,所以一般求可行流。 求解方法 令每条边的流量等于流量下界,得到一个初始流,然后建出这个流的残量网络。 因为初始流的流量不一定...

    %%%liu_runda

    前置技能

    最大流

    定义

    上下界网络流流:每条边的流量除了上界还有下界。
    无源汇上下界可行流:没有源汇的上下界网络流。因为只需要满足每个点流量守恒,所以一般求可行流。

    求解方法

    令每条边的流量等于流量下界,得到一个初始流,然后建出这个流的残量网络。

    因为初始流的流量不一定守恒,所以我们考虑建一个附加流,使得这个附加流加上初始流之后达到守恒。就像这样:
    如果某个点在初始流中满足流量守恒,那么这个点在附加流中也满足流量守恒。
    如果某个点在初始流中流入量比流出量多xx,那么这个点在附加流中的流出量比流入量少xx
    如果某个点在初始流中流入量比流出量少xx,那么这个店在附加流中的流出量比流入量多xx

    而实际上,我们只需要建一个源点ssss和汇点tttt。对于第二种情况,连一条ss>iss−>i的容量为xx的边。第三种情况,连一条i>tti−>tt的容量为x−x的边。如果存在一种可行流使得ss>ttss−>tt满流,那么说明存在可行流。而满流就是求解最大流。此时原网络中每条边的流量就是下界+这条边的流量。

    模板

    ZOJ2314

    #include<cctype>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define N 205
    #define M ((N*(N+1))<<1)
    #define F inline
    #define inf 0x7fffffff
    using namespace std;
    struct edge{ int next,to,v,flow; }ed[M];
    int n,m,k,t,ss,tt,sum,ans; bool f[N];
    int h[N],l[M],cp[N],dis[N],que[N],A[N];
    F char readc(){
        static char buf[100000],*l=buf,*r=buf;
        if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
        if (l==r) return EOF; return *l++;
    }
    F int _read(){
        int x=0; char ch=readc();
        while (!isdigit(ch)) ch=readc();
        while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=readc();
        return x;
    }
    F void writec(int x){ if (x>9) writec(x/10); putchar(x%10+48); }
    F void _write(int x){ writec(x),putchar('\n'); }
    //以上为IO优化
    F void addedge(int x,int y,int z){
        ed[k]=(edge){h[x],y,z,0},h[x]=k++;
        ed[k]=(edge){h[y],x,0,0},h[y]=k++;
    }
    F bool bfs(){
        memset(f,false,sizeof(f));
        int r=0,w=1; dis[ss]=0,f[ss]=true,que[1]=ss;
        while (r<w)
            for (int x=que[++r],i=h[x],v;~i;i=ed[i].next)
                if (!f[v=ed[i].to]&&ed[i].v>ed[i].flow)
                    dis[v]=dis[x]+1,f[v]=true,que[++w]=v;
        return f[tt];
    }
    int dfs(int x,int rem){
        if (x==tt||!rem) return rem; int sum=0;
        for (int &i=cp[x];~i;i=ed[i].next)
            if (dis[ed[i].to]==dis[x]+1){
                int p=dfs(ed[i].to,min(rem,ed[i].v-ed[i].flow));
                if (p) sum+=p,ed[i].flow+=p,ed[i^1].flow-=p,rem-=p;
                if (!rem) break;
            }
        return sum;
    }
    F int mf(){
        int ans=0;
        while (bfs())
            memcpy(cp,h,sizeof(h)),ans+=dfs(ss,inf);
        return ans;
    }
    //以上为Dinic板子
    int main(){
        for (t=_read();t;t--){
            n=_read(),m=_read(),ss=0,tt=n+1;
            memset(h,-1,sizeof(h)),k=sum=0;
            memset(A,0,sizeof(A));//A[]存的就是x
            for (int i=1,x,y,z;i<=m;i++){
                x=_read(),y=_read(),l[i]=_read(),z=_read();
                A[x]-=l[i],A[y]+=l[i],addedge(x,y,z-l[i]);//初始流
            }
            for (int i=1;i<=n;i++)//附加流
                if (A[i]>0) addedge(ss,i,A[i]),sum+=A[i];
                else if (A[i]<0) addedge(i,tt,-A[i]);
            if (mf()!=sum) puts("NO");//是否满流
            else{
                puts("YES");
                for (int i=0;i<(m<<1);i+=2)
                    _write(ed[i].flow+l[i/2+1]);
            }
            if (t>1) putchar('\n');
        }
    }
    展开全文
  • 题目:http://acm.zju.edu.cn/onlinejudge/submit.do 推荐一篇博客 ... 别人已经说很好了,我能做就是给一篇有注释代码 (菜鸡叹气) #include<bits/stdc++.h> using namespace std; cons...

    题目:http://acm.zju.edu.cn/onlinejudge/submit.do

    推荐一篇博客

    https://www.cnblogs.com/liu-runda/p/6262832.html

    别人已经说的很好了,我能做的就是给一篇有注释的代码 (菜鸡的叹气)

     

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn1=200010,maxn2=300;
    //struct edge{
    //	int to,val,nxt,i;
    //}e[maxn1];  //拆成分开的数组,以  e+在结构体中的名称表示 
    int eto[maxn1],eval[maxn1],enxt[maxn1],ei[maxn1]; //将结构体拆成若干数组,速度有明显提升 
    int n,m,inds,sup_beg,sup_end,dinic_flag;
    //inds:建立边的时候辅助计数   sup_beg: 超级源点(super begging) sup_end: 同理  dinic_flag: 当dinic的值等于这个才表示有附加流 
    int head[maxn2],flag[maxn2],deep[maxn2],ans[maxn1],low[maxn1];
    // head: 会dinic的都懂  flag:判断该点是什么不守恒  deep:dinic的都懂,深度♂ low:记录每条线下限 
    inline int gi(){ //这个是快读,也可以用cin/ scanf代替 
        int f=1,sum=0;char ch=getchar();
        while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
        return f*sum;
    }
    void add_edge(int fro,int to,int val,int i){
    	eto[inds]=to; eval[inds]=val; enxt[inds]=head[fro]; ei[inds]=i; head[fro]=inds++; //加正边 
    	eto[inds]=fro; eval[inds]=0; enxt[inds]=head[to]; ei[inds]=i; head[to]=inds++; //反边 
    } // ei:记录这条边在输入时的序号,方便最后输出答案的时候知道是哪个顺序 
    bool bfs(){
    	memset(deep,0,sizeof(deep));
    	queue<int> Q;
    	Q.push(sup_beg);
    	deep[sup_beg]=1;
    	while(!Q.empty()){
    		int now=Q.front(); Q.pop();
    		for(int ind=head[now];ind!=-1;ind=enxt[ind]){
    			int to=eto[ind]; 
    			if(!deep[to]&&eval[ind]){
    				deep[to]=deep[now]+1;
    				Q.push(to);
    			}
    		}
    	}
    	return deep[sup_end];
    }
    int dfs(int num,int flow){
    	if(num==sup_end) return flow;
    	int max_flow=0;
    	for(int ind=head[num];ind!=-1;ind=enxt[ind]){
    		int to=eto[ind];
    		if(deep[to]==deep[num]+1&&eval[ind]){
    			int sto_flow=dfs(to,min(flow,eval[ind]));
    			flow-=sto_flow; //这句一开始我忘记加了 
    			max_flow+=sto_flow;
    			eval[ind]-=sto_flow;
    			eval[ind^1]+=sto_flow;
    			if(flow==0) break;
    		}
    	}
    	if(max_flow==0) deep[num]=0;
    	return max_flow;
    }
    int dinic(){ //dinic嘛。不多解释了,可以看我另外一篇博客 https://blog.csdn.net/weixin_43191865/article/details/88604415 
    	int sum=0;
    	while(bfs()){
    		sum+=dfs(sup_beg,0x3f3f3f3f);
    	}
    	return sum;
    }
    int main(){
    	int cnt=gi();  //快读快读 
    	while(cnt--){
    		n=gi();
    		m=gi();
    		memset(eto,0,sizeof(eto)); memset(eval,0,sizeof(eval)); memset(ei,0,sizeof(ei));
    		memset(enxt,0,sizeof(enxt));
    		memset(head,-1,sizeof(head));
    		memset(flag,0,sizeof(flag));
    		inds=0; sup_beg=0; sup_end=n+1;
    		for(int i=1;i<=m;i++){
    			int fro=gi(),to=gi(),dow=gi(),up=gi(); 
    			add_edge(fro,to,up-dow,i);
    			low[i]=dow;  
    			flag[fro]-=dow; flag[to]+=dow;  
    		}
    		dinic_flag=0;
    		for(int i=1;i<=n;i++){
    			if(flag[i]>0){
    				add_edge(sup_beg,i,flag[i],0);
    				dinic_flag+=flag[i]; //因为边是双向的,只需要记录一边 
    			}
    			if(flag[i]<0){
    				add_edge(i,sup_end,-flag[i],0);
    			}
    		}
    		if(dinic()==dinic_flag){
    			puts("YES");
    			memset(ans,0,sizeof(ans));
    			for(int i=1;i<=n;i++){
    				for(int ind=head[i];ind!=-1;ind=enxt[ind]){
    					int to=eto[ind];
    					if(to==sup_end||ind%2==0) continue; // 只要反边 
    					ans[ei[ind]]=eval[ind]+low[ei[ind]];
    				}
    			}
    			for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    		}
    		else puts("NO");
    	}
    	return 0;
    } 

     

    展开全文
  • ZOJ 1314 Reactor Cooling |...上下界无源汇可行流的模型: 设置虚拟源点和虚拟汇点。 如果一条边\(u \to v\)下界是\(mi\)、上界是\(ma\),则在图中建一条\(u \to v\)边,流量是\(ma - mi\),同时记录\(oud[u] ...

    ZOJ 1314 Reactor Cooling | 上下界无源汇可行流

    题意

    有一个网络,每条边有流量的上界和下界,求一种方案,让里面的流可以循环往复地流动起来。

    题解

    上下界无源汇可行流的模型:

    1. 设置虚拟源点和虚拟汇点。
    2. 如果一条边\(u \to v\)的下界是\(mi\)、上界是\(ma\),则在图中建一条\(u \to v\)的边,流量是\(ma - mi\),同时记录\(oud[u] += mi, ind[v] += mi\),分别代表\(u\)实际比图上多流出的流量与\(v\)实际比图上多流入的流量。
    3. 对于每个节点\(u\),如果\(ind[u] > oud[u]\),即这个节点需要额外流入一些流量,则这些让虚拟源点提供这些流量,即连接一条边\(S \to u\),流量为\(ind[u] - oud[u]\);反之,如果\(ind[u] < oud[u]\),即这个节点需要额外流出一些流量,则这些流量流入了虚拟汇点,即连接一条边\(u \to T\),流量为\(oud[u] - ind[u]\)

    然后求一下这个图的最大流,如果\(S\)的所有出边都流满了,则有解,否则无解。

    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    using namespace std;
    typedef long long ll;
    #define enter putchar('\n')
    #define space putchar(' ')
    template <class T>
    void read(T &x){
        char c;
        bool op = 0;
        while(c = getchar(), c > '9' || c < '0')
        if(c == '-') op = 1;
        x = c - '0';
        while(c = getchar(), c >= '0' && c <= '9')
        x = x * 10 + c - '0';
        if(op) x = -x;
    }
    template <class T>
    void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x >= 10) write(x / 10);
        putchar('0' + x % 10);
    }
    const int N = 205, M = 100005, INF = 0x3f3f3f3f;
    int T, n, m, src, des, ans, sum, u[M], v[M], mi[M], ma[M], ind[N], oud[N];
    int ecnt = 1, adj[N], cur[N], dis[N], nxt[M], go[M], cap[M];
    void init(){
        ans = sum = 0;
        ecnt = 1;
        for(int i = 1; i <= des; i++)
            ind[i] = oud[i] = adj[i] = 0;
    }
    void ADD(int u, int v, int _cap){
        go[++ecnt] = v;
        nxt[ecnt] = adj[u];
        adj[u] = ecnt;
        cap[ecnt] = _cap;
    }
    void add(int u, int v, int _cap){
        ADD(u, v, _cap);
        ADD(v, u, 0);
    }
    bool bfs(){
        static int que[N], qr;
        for(int i = 1; i <= des; i++)
            cur[i] = adj[i], dis[i] = -1;
        dis[src] = 1, que[qr = 1] = src;
        for(int ql = 1; ql <= qr; ql++){
            int u = que[ql];
            for(int e = adj[u], v; e; e = nxt[e])
                if(cap[e] && dis[v = go[e]] == -1){
                    dis[v] = dis[u] + 1, que[++qr] = v;
                    if(v == des) return 1;
                }
        }
        return 0;
    }
    int dfs(int u, int flow){
        if(u == des) return flow;
        int ret = 0, delta;
        for(int &e = cur[u], v; e; e = nxt[e])
            if(cap[e] && dis[v = go[e]] == dis[u] + 1){
                delta = dfs(v, min(cap[e], flow - ret));
                if(delta){
                    cap[e] -= delta;
                    cap[e ^ 1] += delta;
                    ret += delta;
                    if(ret == flow) break;
                }
            }
        return ret;
    }
    int main(){
        read(T);
        while(T--){
            read(n), read(m), src = n + 1, des = n + 2;
            init();
            for(int i = 1; i <= m; i++){
                read(u[i]), read(v[i]), read(mi[i]), read(ma[i]);
                add(u[i], v[i], ma[i] - mi[i]);
                oud[u[i]] += mi[i], ind[v[i]] += mi[i];
            }
            for(int i = 1; i <= n; i++)
                if(ind[i] > oud[i])
                    add(src, i, ind[i] - oud[i]), sum += ind[i] - oud[i];
                else
                    add(i, des, oud[i] - ind[i]);
            while(bfs()) ans += dfs(src, INF);
            if(ans < sum)
                puts("NO");
            else{
                puts("YES");
                for(int i = 1; i <= m; i++)
                    write(mi[i] + cap[i * 2 + 1]), enter;
            }
        }
        return 0;
    }

    转载于:https://www.cnblogs.com/RabbitHu/p/ZOJ1314.html

    展开全文
  • 无源汇可行流例题 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1314 题解: 证明什么就算了,下面给出一种建图方式 1.建虚拟S和T 2.每一条原图边(u,v),设最大容量是Max,最小是Min,建一...
  • 题目链接:https://loj.ac/problem/116无源汇上下界可行流模板题。具体讲解见:http://blog.csdn.net/winter2121/article/details/79430071下面有dinic算法和sap算法。SAP算法中,每条边流量就是反向边cap原图中...
  • 题意:看是否有无源汇上下界可行流,如果有输出流量 题解:对于每一条边u->v,上界high,下界low,来说,我们可以建立每条边流量为high-low,那么这样得到流量可能会不守恒(流入量!=流出量),这时我们要想...
  • 自个设个源点S,汇点T,每个点 du[i]=入度-出度。 du[i]>...T最大流,如果maxflow==sum,则存在可行流,此时每条边流掉流量+它原本下界就是实际流量 dfs过程中某个点可能被多次访问,这...
  • 无源汇上下界可行流就是在一个流量网络中,没有源点和汇点,每条边有流量上下界,要求一种合法方案,并保证流量守恒。 最初想法是转换到最大流来做,令每条边流量为ri−lir_i-l_i,然后跑最大流。不过这样是...
  • 无源汇有上下界可行流(也就是循环流)模型:一个网络,求出一个流,使得每条边流量必须>=Li且, 每个点必须满足总流入量=总流出量(流量守恒)(这个流特点是循环往复,无始无终)可行流算法核心是将一个不满足流量守恒...
  • 无源汇上下界可行流板子题。 无源汇上下界可行流: 1、建虚拟S和T 2、对于原图中上界为Max下界为Min边,连Max-Min边。并用extra[i]记录i多流出(流入)量 3、遍历每个点,如果这个点不满足流量守恒(extra[i...
  • 无源汇上下界网络,,记录一下每个点出去下界进来下界,,,如果IN>OUT,所以,,需要补上IN-OUT自由流量才能在去掉下界之后保持流量平衡 反之,需要掉OUT-IN流量才能保持流量平衡 #include #...
  • 题意:给定一个无源汇网络,求一个可行流,保证每个点流量守恒。(有上下界) 思路:这是个无源汇上下界可行流问题,可以转化成单纯最大流来做,具体理论证明见论文:一种简易方法求解流量有上下界网络中网络...
  • 一般网络流只限制了边流量上界,这里介绍一种变形,限制了边流量上下界,判断是否存在可行流(循环流)。 【算法描述】 我们显然只能借助于最大流算法。下界很讨厌,我们很难在最大流算法中满足对下界限制。...
  • 1.让所有边都下界数量水 2.计算每个点流入水量−-−流出水量d[x]d[x]d[x] 3.建超级源点SSS和超级汇点TTT 4.对于每个点,若d[x]&amp;gt;0d[x]&amp;gt;0d[x]&gt;0则连边S,x,d[x]{S,x,d[x]}S,x,d...
  • 题意: 给n个点,及m根pipe,每根pipe用来躺液体,单向,每时每刻每根pipe进来物质要等于出去物质,要使得m条pipe组成一个循环体,里面躺物质。并且满足每根pipe一定流量限制,范围为[Li,Ri].即要...
  • 题意:有n个点和m条有向边构成的网络。每条边有两个花费: d:毁坏这条边的花费 b:重建一条双向边的花费 ...然后这个无源汇带上下界网络流的可行流问题的求解方法见这里~~ 建图就是上面说的那样啦~...
  • 输入:第一行包含数字N,节点个数和M,管道数量。接下来M行包含4个整数,i,j,lij,cij。没有管道连接到自己。如果有一个管道从i连到j,那么就没有管道从j连到i 输出:如果有办法启动反应堆,第一行输出YES,...
  • 给n个点,及m根pipe,每根pipe用来躺液体,单向,每时每刻每根pipe进来物质要等于出去物质,要使得m条pipe组成一个循环体,里面躺物质。 并且满足每根pipe一定流量限制,范围为[Li,Ri].即要满足...
  • 题意:给n个点,及m根pipe,每根pipe用来躺液体,单向,每时每刻每根pipe进来物质要等于出去物质,要使得m条pipe组成一个循环体,里面躺物质。并且满足每根pipe一定流量限制,范围为[Li,Ri].即要...
  • zoj 2314 Reactor Cooling 无源汇上下界网络题意:有n个点m条边单向无环图。每条边有一个水流上界和下界,水流要大于等于下界小于等于上界,问能否满足这些边约束条件,如果能输出Yes,并输出每条边水流,...
  • 经典的无源汇有上下边界的可行流问题,因为每条边存在最低流量low和最大流量up,所以每条边都至少有low流量,我们为每个边都设置这样的初始流量,这样我们就可以将所有边的下界变为0,上界变成up-low,相当于...
  • 无源汇有上下界可行流 描述 这是一道模板题。 n n n 个点,m m m 条边,每条边 e e e 有一个流量下界 lower(e) \text{lower}(e) lower(e) 和流量上界 upper(e) \text{upper}(e) upper(e),求一种可行方案...
  • 主要思想:每一个点进来的流=出去的流 对于每一个点i,令 Mi= sum(i点所有进来下界)– sum(i点所有出去下界) 如果Mi大于0,代表此点必须还要出去Mi自由,那么我们从源点连一条Mi
  • 题意:有n个点和m条有向边构成的网络,每条边有两个花费: d:毁坏这条边的花费 ...然后这个无源汇带上下界网络流的可行流问题的求解方法见这里~~ 建图就是上面说的那样啦~最后判断有没有可行流就是
  • 无源汇上下界可行流: 每一个边流量有上界下界限制: 每一个点所有汇入流量等于该点所有流出流量 提问:是否存在网路流量满足上述条件? 解决方案: 构建超级源点 source 超级汇点 sink 计算,其中 u ...
  • 思想是,如果存在可行流,每条边必定至少有下界流量思想是,如果存在可行流,每条边必定至少有下界流量思想是,如果存在可行流,每条边必定至少有下界流量 那么直接用下届填充边流量那么直接用下届填充边流量...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 277
精华内容 110
关键字:

无源汇的可行流