首页 > 代码库 > ZOJ--2314--Reactor Cooling【无源汇上下界可行流】
ZOJ--2314--Reactor Cooling【无源汇上下界可行流】
链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1314
题意:某恐怖组织要建立一个核反应堆,他们需要设计一个冷却系统,n个点由m个管子连接,为使液体循环流动,每个节点的总流入量需要等于总流出量,现告诉你每根管子的最小流量及最大流量及它们连接的两点(有向),问是否存在可行流,如存在,输出每个管子的流量。
有上下界的网络流分为四种:无源汇的上下界可行流、有源汇的上下界可行流、有源汇的上下界最大流、有源汇的上下界最小流,这道是其中第一种。
这道题是裸题,直接说这类题的建图方式。
建图:这类题建图一般是建原图的伴随网络,根据伴随网络求是否存在可行流,继而求出每条弧的流量。伴随网络这样建立,新增超级源点Vs和超级汇点Vt,然后对每个顶点u求D(u)值,即流入顶点u的所有边的下界和 减去 流出顶点u的所有边的下界和,然后对于每个顶点u,如果D(u)> 0,新增一条从Vs流向u容量为D(u)的弧,如果D(u)< 0,新增一条从u流向Vt容量为-D(u)的弧,D(u)=0则不添加,D(u)反过来减也可以,网上也有那种减的写法,但是连边时也得反过来,即D(u)> 0时连向Vt,D(u)< 0时从Vs连过来。对于原图中的弧,伴随网络中也要建立,只不过弧的容量变为上界减下界,即一条无最小流限制的弧。
证明方法我不贴了,网上有很多,想法很厉害。
Dinic代码,等我熟练掌握isap模板的时候再贴isap的代码
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 500100 #define eps 1e-7 #define INF 0x7FFFFFFF #define LLINF 0x7FFFFFFFFFFFFFFF #define seed 131 #define mod 1000000007 #define ll long long #define ull unsigned ll #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 struct node{ int u,w,next; int ww; }edge[MAXN]; int head[220],dist[220]; int n,cnt,m,src,sink; int low[50100],D[50100]; void add_edge(int a,int b,int c){ edge[cnt].u = b; edge[cnt].w = c; edge[cnt].next = head[a]; head[a] = cnt++; } bool bfs(){ int i,j; memset(dist,-1,sizeof(dist)); dist[src] = 1; queue<int>q; q.push(src); while(!q.empty()){ int u = q.front(); q.pop(); for(i=head[u];i!=-1;i=edge[i].next){ int v = edge[i].u; if(dist[v]==-1&&edge[i].w){ dist[v] = dist[u] + 1; q.push(v); } } } if(dist[sink]!=-1) return true; return false; } int dfs(int u,int delta){ int i,j,dd; if(u==sink||delta==0) return delta; int ret = 0; for(i=head[u];i!=-1;i=edge[i].next){ int v = edge[i].u; if(dist[v]==dist[u]+1&&edge[i].w){ dd = dfs(v,min(delta,edge[i].w)); edge[i].w -= dd; edge[i^1].w += dd; delta -= dd; ret += dd; } } return ret; } int main(){ int i,j,t; int a,b,c,d; scanf("%d",&t); while(t--){ memset(head,-1,sizeof(head)); memset(D,0,sizeof(D)); scanf("%d%d",&n,&m); cnt = 0; src = http://www.mamicode.com/0;>
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。