上下界网络流

于 2020-04-17 00:15:10 发布
阅读量241 收藏
点赞数
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/Modestr/article/details/105570268
版权

I. DEFINITION

上下界网络问题

  1. 每条边不仅有一个容量上限C，还有容量下限b；
  2. 像普通网络流一样，也要满足除源点汇点外的每一个点， i n x = o u t x in_x=out_x inx​=outx​

II. 无源点汇点上下界可行流（[LOJ]#115. 无源汇有上下界可行流）

因为没有源点和汇点，那么每一个点都需要保证流量守恒；
可行流的意思是可以分配出来，但不要求最大；

Solution:

  1. 对于每一个节点 x x x，流入的下界之和 i n x in_x inx​,流出的下界之和 o u t x out_x outx​,如果 i n x > o u t x in_x>out_x inx​>outx​，那么可理解为多流入的流量来自虚拟源点 s s s，反之流入 T T T
  2. 为了是每一个节点X的流入流出流量守恒，那么应该将较少的那一端的流量往上多分配一些，使得 i n x = o u t x in_x=out_x inx​=outx​,同时往上分配的容量不应该突破该条边的上限 C C C
  3. 跑一遍从 S S S到 T T T的最大流，如果最大流的流量等于 S S S连接所有边的流量之和

TIME COMPLEXITY

与 d i n i c dinic dinic时间复杂度相等
O ( d i n i c ( n 2 ∗ m ) ) O(dinic(n^2*m)) O(dinic(n2∗m))

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
const int INF=0x3f3f3f3f;
int n,m,S,T,cnt=0,maxflow,ans,tot=1,sum;
int head[maxn],dep[maxn],vis[maxn],in[maxn],out[maxn],b[maxn],c[maxn];
inline int read()
{
	int s=0,f=1;
	char c=getchar();
	while (c<'0'||c>'9')
	{
		if (c=='-')
		{
			f=-1;
		}
		c=getchar();
	}
	while (c>='0'&&c<='9')
	{
		s=s*10+c-48;
		c=getchar();
	}
	return s*f;
}
struct node
{
	int from,to,next;
	int val;
}edge[maxn];
inline void add(int x,int y,int z)
{
	edge[++tot].next=head[x];
	edge[tot].from=x;
	edge[tot].to=y;
	edge[tot].val=z;
	head[x]=tot;
	edge[++tot].next=head[y];
	edge[tot].from=y;
	edge[tot].to=x;
	edge[tot].val=0;
	head[y]=tot;
}
inline bool bfs()
{
	queue<int>q;
	memset(dep,-1,sizeof(dep));
	dep[S]=1;
	q.push(S);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=edge[i].next)
		{
			int to=edge[i].to,w=edge[i].val;
			if(dep[to]==-1&&w>0)
			{
				dep[to]=dep[u]+1;
				q.push(to);
			}
		}
	}
	if (dep[T]==-1)
	{
		return 0;
	}
	return 1;
}
inline int dfs(int u,int low)
{
	if (u==T)
	{
		return low;
	}
	int ret=low;
	for (int i=head[u];i;i=edge[i].next)
	{
		int to=edge[i].to,w=edge[i].val;
		if (dep[to]==dep[u]+1&&w>0)
		{
			int flow=dfs(to,min(ret,w));
			if (flow>0)
			{
				edge[i].val-=flow;
				edge[i^1].val+=flow;
			}
			ret-=flow;
			if (!ret)
			{
				break;
			}
		}
	}
	return low-ret;
}
inline void dinic()
{
    while (bfs())
    {
		maxflow+=dfs(S,INF);
	}
}
int main()
{
	n=read(),m=read();
	S=0,T=n+1;
	for (int i=1;i<=m;i++)
	{
		int x=read(),y=read();
		b[i]=read(),c[i]=read();
		add(x,y,c[i]-b[i]);
		in[y]+=b[i];
		out[x]+=b[i];
	}
	for (int i=1;i<=n;i++)
	{
		int dif=in[i]-out[i];
		if (dif>0)
		{
			add(S,i,dif);
			sum+=dif;
		}
		else
		{
			add(i,T,out[i]-in[i]);
		}
	}
//	dinic();
	while (bfs())                   //从S到T跑最大流
    {
		maxflow+=dfs(S,INF);
	}
	if (maxflow!=sum)
	{
		cout<<"NO"<<endl;
		return 0;
	}
	else
	{
		cout<<"YES"<<endl;
		for (int i=1;i<=m;i++)
		{
			//注意最后加的浮动流量应该是反边的流量 edge[(i<<1)|1]，正向边是剩余的流量
			//反边要不要异或1取决于tot从几开始
			cout<<edge[(i<<1)|1].val+b[i]<<endl;
		}
	}
	return 0;
}

III. 有源点汇点上下界可行流

S S S和 T T T不需要守恒。将 T T T向 S S S建一条下界为零，上界为 I N F INF INF的边
流量为 t t t到 S S S的反边的流量

与上一题几乎一模一样

IV. 有源点汇点上下界最大流（[LOJ]#116. 有源汇有上下界最大流）

Solution:

在可行流的前提下满足最大流

  1. 按照无源点汇点上下界可行流建图
  2. 额外添加 t t t到 s s s的边，容量下界为 0 0 0，上界为 I N F INF INF
  3. 跑一遍 S S S到 T T T的最大流，得到一个可行流 f l o w 1 flow1 flow1
  4. 删掉 t t t到 s s s的边跑一遍 s s s到 t t t的最大流，得到 f l o w 2 flow2 flow2
  5. a n s = f l o w 1 + f l o w 2 ans=flow1+flow2 ans=flow1+flow2

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
const int INF=0x3f3f3f3f;
int n,m,s,t,S,T,cnt=0,maxflow,ans,tot=1,sum,flow,flow1,flow2;
int head[maxn],dep[maxn],vis[maxn],in[maxn],out[maxn],b[maxn],c[maxn];
inline int read()
{
	int s=0,f=1;
	char c=getchar();
	while (c<'0'||c>'9')
	{
		if (c=='-')
		{
			f=-1;
		}
		c=getchar();
	}
	while (c>='0'&&c<='9')
	{
		s=s*10+c-48;
		c=getchar();
	}
	return s*f;
}
struct node
{
	int from,to,next;
	int val;
}edge[maxn];
inline void add(int x,int y,int z)
{
	edge[++tot].next=head[x];
	edge[tot].from=x;
	edge[tot].to=y;
	edge[tot].val=z;
	head[x]=tot;
	edge[++tot].next=head[y];
	edge[tot].from=y;
	edge[tot].to=x;
	edge[tot].val=0;
	head[y]=tot;
}
inline bool bfs()
{
	queue<int>q;
	memset(dep,-1,sizeof(dep));
	dep[S]=1;
	q.push(S);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=edge[i].next)
		{
			int to=edge[i].to,w=edge[i].val;
			if(dep[to]==-1&&w>0)
			{
				dep[to]=dep[u]+1;
				q.push(to);
			}
		}
	}
	if (dep[T]==-1)
	{
		return 0;
	}
	return 1;
}
inline int dfs(int u,int low)
{
	if (u==T)
	{
		return low;
	}
	int ret=low;
	for (int i=head[u];i;i=edge[i].next)
	{
		int to=edge[i].to,w=edge[i].val;
		if (dep[to]==dep[u]+1&&w>0)
		{
			int flow=dfs(to,min(ret,w));
			if (flow>0)
			{
				edge[i].val-=flow;
				edge[i^1].val+=flow;
			}
			ret-=flow;
			if (!ret)
			{
				break;
			}
		}
	}
	return low-ret;
}
inline void dinic()
{
    while (bfs())
    {
		maxflow+=dfs(S,INF);
	}
}
int main()
{
	n=read(),m=read(),s=read(),t=read();
	tot=1;
	for(int i = 1; i <= m; i++)
	{
		int x=read(),y=read();
		b[i]=read(),c[i]=read();
		in[y]+=b[i];
		out[x]+=b[i];
		add(x,y,c[i]-b[i]);
	}
	S=0,T=n+1;                                  //虚拟源点和汇点
	for (int i=1;i<=n;i++)
	{
		if (in[i]-out[i]>0)
		{
			add(S,i,in[i]-out[i]);
			sum=sum+(in[i]-out[i]);
		}
		else
		{
			add(i,T,out[i]-in[i]);
		}
	}
	add(t,s,INF); 								//添加1条 t到s的边，容量inf。反边也需要，容量为0
	//寻找可行流
	while (bfs()==true)                         //从S到T跑最大流
	{
		flow=dfs(S,INF);
		maxflow+=flow;
	}
	if (maxflow!=sum)
	{
		cout<<"please go home to sleep"<<"\n";
		return 0;
	}
	flow1=edge[tot].val;                        //记录“可行流”的大小，注意应该取t到s的反边的流量
	edge[tot].val=edge[tot-1].val=0;            //删掉 t到s的边，等效于将流量设为0
	//跑一边s到t的最大流
	S=s,T=t;
	flow=0;
	flow2=0;
	while (bfs()==true)                         //跑最大流
	{
		flow=dfs(S,INF);
		flow2+=flow;
	}
	cout<<flow1+flow2<<endl;                    //可行流+最大流 得到最终的最大流
	return 0;
}

V. 有源点汇点上下界最小流

Solution：

  1. 按照有源点汇点上下界可行流建图，求出 f l o w 1 flow1 flow1
  2. 删掉 t t t到 s s s的边，跑一边原图 t t t到 s s s的最大流，得到 f l o w 2 flow2 flow2
  3. a n s = f l o w 1 − f l o w 2 ans=flow1-flow2 ans=flow1−flow2

Notice:这题链式前向星用结构体会TLE一个点！！！

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
const int INF=0x3f3f3f3f;
int n,m,s,t,S,T,cnt,maxflow,ans,tot=1,sum,flow,flow1,flow2;
int head[maxn],to[maxn],edge[maxn],nxt[maxn],dep[maxn],vis[maxn],in[maxn],out[maxn],b[maxn],c[maxn];
inline int read()
{
	int s=0,f=1;
	char c=getchar();
	while (c<'0'||c>'9')
	{
		if (c=='-')
		{
			f=-1;
		}
		c=getchar();
	}
	while (c>='0'&&c<='9')
	{
		s=s*10+c-48;
		c=getchar();
	}
	return s*f;
}
inline void add(int x,int y,int z)
{
	to[++tot]=y;
	edge[tot]=z;
	nxt[tot]=head[x];
	head[x]=tot;
	to[++tot]=x;
	edge[tot]=0;
	nxt[tot]=head[y];
	head[y]=tot;
}
inline bool bfs()
{
	queue<int>q;
	memset(dep,-1,sizeof(dep));
	dep[S]=1;
	q.push(S);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=nxt[i])
		{
			int To=to[i],w=edge[i];
			if (dep[To]==-1&&w>0)
			{
				dep[To]=dep[u]+1;
				q.push(To);
			}
		}
	}
	if (dep[T]==-1)
	{
		return 0;
	}
	return 1;
}
inline int dfs(int u,int low)
{
	if (u==T)
	{
		return low;
	}
	int ret=low;
	for (int i=head[u];i;i=nxt[i])
	{
		int To=to[i],w=edge[i];
		if (dep[To]==dep[u]+1&&w>0)
		{
			int flow=dfs(To,min(ret,w));
			if (flow==0)
			{
				dep[To]=0;
			}
			if (flow>0)
			{
				edge[i]-=flow;
				edge[i^1]+=flow;
			}
			ret-=flow;
			if (!ret)
			{
				break;
			}
		}
	}
	return low-ret;
}
inline void dinic()
{
    while (bfs())
    {
		maxflow+=dfs(S,INF);
	}
}
signed main()
{
	n=read(),m=read(),s=read(),t=read();
	tot=1;
	for(int i=1;i<=m;i++)
	{
		int x=read(),y=read();
		b[i]=read(),c[i]=read();
		in[y]+=b[i];
		out[x]+=b[i];
		add(x,y,c[i]-b[i]);
	}
	S=0,T=n+1;                                  //虚拟源点和汇点
	for (int i=1;i<=n;i++)
	{
		if (in[i]-out[i]>0)
		{
			add(S,i,in[i]-out[i]);
			sum=sum+(in[i]-out[i]);
		}
		else
		{
			add(i,T,out[i]-in[i]);
		}
	}
	add(t,s,INF); 								//添加1条 t到s的边，容量inf。反边也需要，容量为0
	//寻找可行流
	while (bfs()==true)                         //从S到T跑最大流
	{
		flow=dfs(S,INF);
		maxflow+=flow;
	}
	if (maxflow!=sum)
	{
		cout<<"please go home to sleep"<<"\n";
		return 0;
	}
	flow1=edge[tot];                        //记录“可行流”的大小，注意应该取t到s的反边的流量
	edge[tot]=edge[tot-1]=0;            //删掉 t到s的边，等效于将流量设为0
	//跑一边s到t的最大流
	S=t,T=s;
	flow=0;
	flow2=0;
	while (bfs()==true)                         //跑最大流
	{
		flow=dfs(S,INF);
		flow2+=flow;
	}
	cout<<flow1-flow2<<endl;                    //可行流+最大流 得到最终的最大流
	return 0;
}
//链式前向星用struct会T!!!
/*
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=500005;
const int INF=0x3f3f3f3f;
int n,m,s,t,S,T,cnt=0,maxflow,ans,tot=1,sum,flow,flow1,flow2;
int head[maxn],dep[maxn],vis[maxn],in[maxn],out[maxn],b[maxn],c[maxn];
inline int read()
{
	int s=0,f=1;
	char c=getchar();
	while (c<'0'||c>'9')
	{
		if (c=='-')
		{
			f=-1;
		}
		c=getchar();
	}
	while (c>='0'&&c<='9')
	{
		s=s*10+c-48;
		c=getchar();
	}
	return s*f;
}
struct node
{
	int from,to,next;
	int val;
}edge[maxn];
inline void add(int x,int y,int z)
{
	edge[++tot].next=head[x];
	edge[tot].from=x;
	edge[tot].to=y;
	edge[tot].val=z;
	head[x]=tot;
	edge[++tot].next=head[y];
	edge[tot].from=y;
	edge[tot].to=x;
	edge[tot].val=0;
	head[y]=tot;
}
inline bool bfs()
{
	queue<int>q;
	memset(dep,-1,sizeof(dep));
	dep[S]=1;
	q.push(S);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=edge[i].next)
		{
			int to=edge[i].to,w=edge[i].val;
			if(dep[to]==-1&&w>0)
			{
				dep[to]=dep[u]+1;
				q.push(to);
			}
		}
	}
	if (dep[T]==-1)
	{
		return 0;
	}
	return 1;
}
inline int dfs(int u,int low)
{
	if (u==T)
	{
		return low;
	}
	int ret=low;
	for (int i=head[u];i;i=edge[i].next)
	{
		int to=edge[i].to,w=edge[i].val;
		if (dep[to]==dep[u]+1&&w>0)
		{
			int flow=dfs(to,min(ret,w));
			if (flow>0)
			{
				edge[i].val-=flow;
				edge[i^1].val+=flow;
			}
			ret-=flow;
			if (!ret)
			{
				break;
			}
		}
	}
	return low-ret;
}
inline void dinic()
{
    while (bfs())
    {
		maxflow+=dfs(S,INF);
	}
}
signed main()
{
	n=read(),m=read(),s=read(),t=read();
	tot=1;
	for(int i = 1; i <= m; i++)
	{
		int x=read(),y=read();
		b[i]=read(),c[i]=read();
		in[y]+=b[i];
		out[x]+=b[i];
		add(x,y,c[i]-b[i]);
	}
	S=0,T=n+1;                                  //虚拟源点和汇点
	for (int i=1;i<=n;i++)
	{
		if (in[i]-out[i]>0)
		{
			add(S,i,in[i]-out[i]);
			sum=sum+(in[i]-out[i]);
		}
		else
		{
			add(i,T,out[i]-in[i]);
		}
	}
	add(t,s,INF); 								//添加1条 t到s的边，容量inf。反边也需要，容量为0
	//寻找可行流
	while (bfs()==true)                         //从S到T跑最大流
	{
		flow=dfs(S,INF);
		maxflow+=flow;
	}
	if (maxflow!=sum)
	{
		cout<<"please go home to sleep"<<"\n";
		return 0;
	}
	flow1=edge[tot].val;                        //记录“可行流”的大小，注意应该取t到s的反边的流量
	edge[tot].val=edge[tot-1].val=0;            //删掉 t到s的边，等效于将流量设为0
	//跑一边s到t的最大流
	S=t,T=s;
	flow=0;
	flow2=0;
	while (bfs()==true)                         //跑最大流
	{
		flow=dfs(S,INF);
		flow2+=flow;
	}
	cout<<flow1-flow2<<endl;                    //可行流+最大流 得到最终的最大流
	return 0;
}
*/

VI. 无源点汇点上下界最小费用可行流

Solution:

  1. 按照无源点汇点上下界可行流建图，把原图中 x − > y x->y x−>y 的边，建一条容量 u p p e r − l o w e r upper-lower upper−lower，费用为 c o s t cost cost的边，其他边的费用设为 0 0 0即可
  2. 跑最小费用最大流即可
  3. 最终最小的费用 = = == ==所有边的下界流量*对应的费用的和 + + +最小费用最大流的费用

VII. 有源点汇点上下界最小费用可行流

Solution：

在VI的基础上，额外增加一条t到s的边，容量是INF，费用为0；

VIII. [LGOJ]P4043 [AHOI2014/JSOI2014]支线剧情

Solution：

  1. 对于一条边 x − > y x->y x−>y，容量下界设为 1 1 1，上界设为 I N F INF INF，表示每个剧情最多被覆盖一次，上不封顶；费用就是时间
  2. 原图中源点 s : 1 s:1 s:1，汇点 t : 0 t:0 t:0， 1 1 1到 n n n的每个点 i i i都向 t t t连一条下界为 0 0 0，上界 I N F INF INF，费用为 0 0 0的边，意思是没个点都可以终结剧情
  3. 然后统计每个点的 i n x in_x inx​， o u t x out_x outx​按照无源点汇点建图，要么是 S S S连 x x x，要么是 x x x连 T T T，费用都设为 0 0 0，容量就是 i n x in_x inx​和 o u t x out_x outx​之差；
  4. 额外的一条边 t t t到 s s s，容量 I N F INF INF，费用 0 0 0；
  5. 跑一边从 S S S到 T T T的最小费用最大流 c o s t 2 cost2 cost2，再统计每条边的下界流量*对应费用的和 c o s t 1 cost1 cost1； c o s t 1 + c o s t 2 cost1+cost2 cost1+cost2

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
const int inf=0x3f3f3f3f;
int n,s=1,t,S,T,tot=1,maxflow,cost1,cost2;
int head[maxn],pre[maxn],level[maxn],in[maxn],out[maxn],dis[maxn],increase[maxn];
bool vis[maxn];
struct node
{
	int from,to,next,flow,cost;
}edge[maxn];
inline int read()
{
	int s=0,f=1;
	char c=getchar();
	while (c<'0'||c>'9')
	{
		if (c=='-')
		{
			f=-1;
		}
		c=getchar();
	}
	while (c>='0'&&c<='9')
	{
		s=s*10+c-48;
		c=getchar();
	}
	return s*f;
}
inline void add(int x,int y,int z,int f)
{
	edge[++tot].next=head[x];
	edge[tot].to=y;
	edge[tot].flow=z;
	edge[tot].cost=f;
	head[x]=tot;
	
	edge[++tot].next=head[y];
	edge[tot].to=x;
	edge[tot].flow=0;
	edge[tot].cost=-f;
	head[y]=tot;
}
inline bool spfa()
{
	memset(vis,0,sizeof(vis));
	memset(dis,0x7f,sizeof(dis));
	memset(increase,0x7f,sizeof(increase));
	queue<int> q;
	q.push(S);
	vis[S]=true;
	dis[S]=0;
	while (q.empty()==false)
	{
		int x=q.front();
		q.pop();
		vis[x]=false;
		for (int i=head[x];i;i=edge[i].next)
		{
			int y=edge[i].to;
			if (edge[i].flow>0&&dis[x]+edge[i].cost<dis[y])
			{
				dis[y]=dis[x]+edge[i].cost;
				increase[y]=min(increase[x],edge[i].flow);
				pre[y]=i;
				if (vis[y]==false)
				{
					q.push(y);
					vis[y]=true;
				}
			}
		}
	}
	return dis[T]<0x7f7f7f7f;
}

inline void update()
{
	int cur=T;
	while (cur!=S)
	{
		int last=pre[cur];
		edge[last].flow-=increase[T];
		edge[last^1].flow+=increase[T];
		cur=edge[last^1].to;
	}
	maxflow+=increase[T];
	cost2+=dis[T]*increase[T];
	return ;
}

int main()
{
	n=read();
	for (int i=1;i<=n;i++)
	{
		int k=read();
		if (i!=1)
		{
			add(i,t,inf,0);
		}
		for (int j=1;j<=k;j++)
		{
			int nxt=read(),tim=read();
			in[nxt]+=1;
			out[i]+=1;
			cost1=cost1+1*tim;
			add(i,nxt,inf-1,tim);
		}
	}
	S=n+1,T=n+2;
	for (int i=0;i<=n;i++)
	{
		if (in[i]-out[i]>0)
		{
			add(S,i,in[i]-out[i],0);
		}
		else
		{
			add(i,T,out[i]-in[i],0);
		}
	}
	add(t,s,inf,0);
	while (spfa()==true)
	{
		update();
	}
	cout<<cost1+cost2<<endl;
	return 0;
}
/*
6
2 2 1 3 2
2 4 3 5 4
2 5 5 6 6
0
0
0
*/
SGU 176 Flow construction 有源汇上下界网络流 最小流
inf_force
09-10 883
SGU 176 Flow construction 有源汇上下界网络流 最小流题意：有n个节点m根水管的网络，每根水管有个水流的限制，问最少要多少水流能满足整个网络。最小流 代码：//author: CHC //First Edit Time: 2015-09-10 10:45 #include <iostream> #include <cstdio> #include <cstring>
有上下界的网络流学习笔记
weixin_30824479的博客
01-08 172
//其实主要还是自己复习用 //假定读者能够熟练打dinic的板子 有上下界的网络流的核心是”调整”,我们通过一个初始的未必可行的流调整出一个可行流,还可以从可行的未必最大/最小的流调整出最大/最小流. 另一个常用技巧是有源汇的流和无源汇的流(循环流)的转换.除了无源汇可行流的求解,其他有源汇的上下界网络流都要用到这个技巧. 无源汇有上下界可行流(也就是循环流) 模型:一个网络,...
有上下界的网络流
AZUI _ oi memories
01-05 599
我是在心情极度不爽且精神很疲惫的情况下写的这篇博客。可能语无伦次，见谅。 上下界网络流，大致思路是虚拟超级源点和汇点(ss&tt)，让每个点的流量底线强行用超级源点和超级汇点来满足。 具体来讲，分为无源汇（求循环流），有源汇（求满足限制的最大流、最小流）。 具体原理不想写了，实现的时候求最大流有两种写法：用ss&tt先跑一次，然后删ss和tt在利用原来的s和t跑一次两者加起来，或者不删点直接
5.有上下界的网络流_有上下界的网络流_
10-03
有上下界的网络流是图论中的一个重要概念，它在计算机科学和运筹学中有着广泛的应用，尤其是在解决运输问题、电路设计、资源分配等问题时。网络流问题通常涉及到在一个有向图中，从一个源节点到一个汇点，通过网络中...
有上下界网络流问题
11-26
在转化网络中，所有的流量限制都转化为单一的容量限制，使得原本的有上下界网络流问题转化为无上下界网络流问题，从而可以使用这些算法进行求解。 在完成最大流求解后，如何判断原问题中是否存在可行的流呢？一种...
浅谈上下界网络流
linkfqy
07-07 5010
背景最近一直在做这类题目…… 感觉题目变化还是挺多的 就在这里总结一下好了……首先Orz Lynstery 本文参考博客：有上下界的网络流学习笔记——by liu_runda正文上下界网络流，显然就是对每条边有上下界流量限制的网络流问题 众人：这不废话嘛 对于上下界网络流问题，最重要的思想是“转化” 因为学习后你会发现：处理每一种情形都是要由前一种更为简单的情形转化过来，然后用同样的方法
上下界网络流 cf704D
rgndao的博客
04-05 204
cf704D 给棋盘上n个棋子染色，红黑两种，代价不同，有m个约束，要求某一行或某一列的红黑棋子数差不能超过某一数值。求最小代价的染色方案。 上下界网络流的思路就是分别减去最低流量，剩余的放在图中跑最大流，对于原有大于零下界的边就通过新建超级源点ss和汇点tt解决，即出点多出的连向汇点，入点缺少的从源点补充。合法要求：源点s发出的必须能跑满，否则原有的平衡条件就打破了，无可行流。 对于原本就...
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值