以无源汇上下界可行流为基础，如果有源点汇点呢，源点汇点是不必平衡的，我们要转变成无源汇的，那么源点流出的就要有一个汇点流入源点，同理也需要汇点流出，那很简单了，从当前汇点引一条边到当前源点，容量为inf即可，然后跑无源汇有上下界可行流就好啦
这样跑出来一个后，如何调整到最大流 / 最小流呢？
求最大流应该好做一点，从s 到 t的残流网络，跑一跑最大流就好了，最后的可行流最大流量就是 ： 最初可行流流量 + s - t残流最大流流量
稍微整理一下：
有源汇上下界可行流：
·根据题意建图
·汇点 到 源点 连入容量无穷大的边 转变为无源汇上下界可行流（循环流）
·添加附加流 跑Dinic
·得到基础可行流
·删除附加流的边，依照初始源点汇点和残流网络再跑DInic
·得到最后的有源汇上下界可行最大流 = 第一次Dinic后从初始汇点留到源点的流量 + 残流网络最大流的流量
·每条边的流量 = 最低限流 + 对应逆向边的流量
例题ZOJ3229
n天 m个人
每个人至少gx张
每天 有C个不同目标 且至多排 D张
C个目标 ： 目标号 必须要拍l r张
依据输入建完图后，就是典型的有源汇上下界可行流了
先来看一下经典的初始化模板
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inf (1 << 28)
using namespace std;
const int maxn = 2005,maxm=1e5+1e2;
//前向星
struct node{
int to,val,lid,pre;
}e[maxm];
int id[maxn],cnt = 0;
//dinic
int cur[maxn];
int flor[maxn];//BFS的分层处理
int totid;
int n,m;//基础变量
int upflow[maxn];//差流（可升流）
int retf[maxm];//结果
int low[maxm];//下界
void init()
{
memset(id,-1,sizeof(id));
memset(upflow,0,sizeof(upflow));
cnt = 0;
}
//网络流加边
void add(int from,int to,int val,int lid)
{
e[cnt].lid = lid;
e[cnt].to = to;
e[cnt].val = val;
e[cnt].pre = id[from];
id[from] = cnt++;
swap(from,to);
e[cnt].lid = lid;
e[cnt].to = to;
e[cnt].val = 0;
e[cnt].pre = id[from];
id[from] = cnt++;
}
//Dinic
//bfs分层
bool bfs(int s,int t)
{
memset(flor,0,sizeof(flor));
flor[s] = 1;
queue<int> q;
while(q.size())q.pop();
q.push(s);
while(q.size())
{
int now = q.front();
q.pop();
for(int i = id[now];~i;i = e[i].pre)
{
int to = e[i].to;
int val = e[i].val;
if(val > 0 && flor[to] == 0)
{
flor[to] = flor[now] + 1;
//printf("%d flor = %d
",to,flor[to]);
q.push(to);
if(to == t)return 1;
}
}
}
return 0;
}
int dfs(int s,int t,int value)
{
//printf("s t value = ::: %d %d %d
",s,t,value);
if(s == t || value == 0)return value;
int ret = value,a;
for(int &i = cur[s];~i;i = e[i].pre)
{
int to = e[i].to;
int val = e[i].val;
//printf("to = %d val = %d flornow = %d florto = %d
",to,val,flor[s],flor[to]);
if(flor[to] == flor[s] + 1 && (a = dfs(to,t,min(ret,val))))
{
//printf("a = %d
",a);
e[i].val -= a;
e[i^1].val += a;
ret -= a;
if(ret == 0)break;
}
}
if(ret == value)flor[s] = 0;
return value - ret;
}
int dinic(int s,int t)
{
int ret = 0;
while(bfs(s,t))
{
memcpy(cur,id,sizeof(id));
ret += dfs(s,t,inf);
//cout<<ret<<endl;
}
return ret;
}
对于已有的边我要记录流量差，以提供给附加流增流依据
void addflow(int from,int to,int low,int up,int lid)
{
upflow[from] -= low;
upflow[to] += low;
add(from,to,up-low,lid);
}
对于我们新增加的源点汇点就不用啦
剩下的操作我就一main到底了…………
根据题意建边，存储最低限流
init();
s = 0;t = n + m + 1;
ss = t + 1;
tt = t + 2;
totid = 0;
for(int i = 1;i <= m;++i)
{
scanf("%d",&peoplelim);
addflow(n+i,t,peoplelim,inf,0);
}
int targetnum,daylim;
for(int i = 1;i <= n;++i)//天
{
scanf("%d%d",&targetnum,&daylim);
addflow(s,i,0,daylim,0);
for(int j = 1;j <= targetnum;j++)
{
int targetid,l,r;
scanf("%d%d%d",&targetid,&l,&r);
addflow(i,n+1+targetid,l,r,++totid);
low[totid] = l;
}
}
转变无源汇，求出基本可行流
int sum = 0;
for(int i = s;i <= t;++i)
{
if(upflow[i] < 0)
add(i,tt,-upflow[i],0);
else
{
sum += upflow[i];
add(ss,i,upflow[i],0);
}
}
add(t,s,inf,0);
存在基本可行流
删除添加的边，在原来的有源汇图中跑一遍残流网络最大流
if(dinic(ss,tt) == sum)
{
//删边
for(int i = id[ss];~i;i = e[i].pre)
{
e[i].val = e[i^1].val = 0;
}
for(int i = id[tt];~i;i = e[i].pre)
{
e[i].val = e[i^1].val = 0;
}
int baseflow = e[cnt-1].val;
e[cnt - 1].val = e[cnt - 2].val = 0;
printf("%d
",baseflow + dinic(s,t));
for(int now = 1;now <= m;++now)
{
for(int i = id[n+now];~i;i = e[i].pre)
{
int lid = e[i].lid;
if(lid == 0)continue;
if(i % 2 == 0)continue;
retf[lid] = e[i].val + low[lid];
}
}
for(int i=1;i<=totid;++i)printf("%d
",retf[i]);
}
else
{
printf("-1
");
}
完整代码：
/**
n天 m个人
每个人至少gx张
每天 有C个不同目标 且至多排 D张
C个目标 ： 目标号 必须要拍l r张
**/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inf (1 << 28)
using namespace std;
const int maxn = 2005,maxm=1e5+1e2;
//前向星
struct node{
int to,val,lid,pre;
}e[maxm];
int id[maxn],cnt = 0;
//dinic
int cur[maxn];
int flor[maxn];//BFS的分层处理
int totid;
int n,m;//基础变量
int upflow[maxn];//差流（可升流）
int retf[maxm];//结果
int low[maxm];//下界
void init()
{
memset(id,-1,sizeof(id));
memset(upflow,0,sizeof(upflow));
cnt = 0;
}
//网络流加边
void add(int from,int to,int val,int lid)
{
e[cnt].lid = lid;
e[cnt].to = to;
e[cnt].val = val;
e[cnt].pre = id[from];
id[from] = cnt++;
swap(from,to);
e[cnt].lid = lid;
e[cnt].to = to;
e[cnt].val = 0;
e[cnt].pre = id[from];
id[from] = cnt++;
}
//Dinic
//bfs分层
bool bfs(int s,int t)
{
memset(flor,0,sizeof(flor));
flor[s] = 1;
queue<int> q;
while(q.size())q.pop();
q.push(s);
while(q.size())
{
int now = q.front();
q.pop();
for(int i = id[now];~i;i = e[i].pre)
{
int to = e[i].to;
int val = e[i].val;
if(val > 0 && flor[to] == 0)
{
flor[to] = flor[now] + 1;
//printf("%d flor = %d
",to,flor[to]);
q.push(to);
if(to == t)return 1;
}
}
}
return 0;
}
int dfs(int s,int t,int value)
{
//printf("s t value = ::: %d %d %d
",s,t,value);
if(s == t || value == 0)return value;
int ret = value,a;
for(int &i = cur[s];~i;i = e[i].pre)
{
int to = e[i].to;
int val = e[i].val;
//printf("to = %d val = %d flornow = %d florto = %d
",to,val,flor[s],flor[to]);
if(flor[to] == flor[s] + 1 && (a = dfs(to,t,min(ret,val))))
{
//printf("a = %d
",a);
e[i].val -= a;
e[i^1].val += a;
ret -= a;
if(ret == 0)break;
}
}
if(ret == value)flor[s] = 0;
return value - ret;
}
int dinic(int s,int t)
{
int ret = 0;
while(bfs(s,t))
{
memcpy(cur,id,sizeof(id));
ret += dfs(s,t,inf);
//cout<<ret<<endl;
}
return ret;
}
void addflow(int from,int to,int low,int up,int lid)
{
upflow[from] -= low;
upflow[to] += low;
add(from,to,up-low,lid);
}
int main()
{
int s,t;//初始源汇
int ss,tt;//无源汇有上下界可行流种附加流的源汇
int peoplelim;//每个人至少拍的张数
while(~scanf("%d%d",&n,&m))
{
init();
s = 0;t = n + m + 1;
ss = t + 1;
tt = t + 2;
totid = 0;
for(int i = 1;i <= m;++i)
{
scanf("%d",&peoplelim);
addflow(n+i,t,peoplelim,inf,0);
}
int targetnum,daylim;
for(int i = 1;i <= n;++i)//天
{
scanf("%d%d",&targetnum,&daylim);
addflow(s,i,0,daylim,0);
for(int j = 1;j <= targetnum;j++)
{
int targetid,l,r;
scanf("%d%d%d",&targetid,&l,&r);
addflow(i,n+1+targetid,l,r,++totid);
low[totid] = l;
}
}
//bound_flow();//有源汇上下界可行最大流
int sum = 0;
for(int i = s;i <= t;++i)
{
if(upflow[i] < 0)
add(i,tt,-upflow[i],0);
else
{
sum += upflow[i];
add(ss,i,upflow[i],0);
}
}
add(t,s,inf,0);
if(dinic(ss,tt) == sum)
{
for(int i = id[ss];~i;i = e[i].pre)
{
e[i].val = e[i^1].val = 0;
}
for(int i = id[tt];~i;i = e[i].pre)
{
e[i].val = e[i^1].val = 0;
}
int baseflow = e[cnt-1].val;
e[cnt - 1].val = e[cnt - 2].val = 0;
printf("%d
",baseflow + dinic(s,t));
for(int now = 1;now <= m;++now)
{
for(int i = id[n+now];~i;i = e[i].pre)
{
int lid = e[i].lid;
if(lid == 0)continue;
if(i % 2 == 0)continue;
retf[lid] = e[i].val + low[lid];
}
}
for(int i=1;i<=totid;++i)printf("%d
",retf[i]);
}
else
{
printf("-1
");
}
printf("
");
}
}