题意分析
给出n个结点，m条管道，每条管道存在最小流量和最大流量，而且每个结点的流入量等于流出流出量，问这n个结点和m条管道能否形成流量循环
解题思路
经典的无源汇有上下边界的可行流问题，因为每条边存在最低流量low和最大流量up，所以每条边都至少有low流量，我们为每个边都设置这样的初始流量，这样我们就可以将所有边的下界变为0，上界变成up-low，相当于消灭了下界，而up-low则表示这条边的容量，和普通最大流问题类似，就将原来有上下边界的边转化为容量为up-low的边
而这类问题是没有源点和汇点的，那么我们再构建一对源点汇点即可。
处理好了上下界问题，我们还需要处理另一个核心问题：每个点的流入量等于流出量，因为我们为每条边分配了初始流量，那么对于每个点，有一个初始的流入流出量之差 a[i] = i 点的初始流入量-i点的初始流出量
1）如果a[i] > 0 ，说明流入量过多，那么将多余的流入量视作由源点流入，即由源点向i建一条容量为a[i]的边
2）如果a[i] < 0 ，说明输出量过多，那么将多余的流出量视作流入汇点的，即由i向汇点建一条容量为 |a[i]| 的边
我们用s_out记录源点的总流出量，如果构建的图中的最大流 max_flow == s_out ，说明流量由s 流入原图再流出至汇点的过程中，没有流量损失，这说明原图是流量循环的，而在求最大流的过程中，我们已经将每条边的容量调整好了，即满足条件，那么每条边的实际流量就是 下界+实际流量
代码区
（因为ZOJ暂时交不了这个题，所以我是用别人的标称对拍很久后，得出的代码，如果ZOJ修复了，我会给出通过评测的代码）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<string>
#include<fstream>
#include<vector>
#include<stack>
#include <map>
#include <iomanip>
#define bug cout << "**********" << endl
#define show(x, y) cout<<"["<<x<<","<<y<<"] "
#define LOCAL = 1;
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int Max = 1e5 + 10;
const int Max2 = 3e2 + 10;
struct Edge
{
int to, flow, next;
} edge[Max << 1];
int n, m, s, t;
int head[Max], tot;
int dis[Max], cur[Max];
int a[Max]; //记录i在初始流中的流入量-流出量
int in[Max]; //in 记录管道的初始流量，即下界;
int id[Max]; //记录水管i在残余网络中的反向边编号
void init()
{
memset(head, -1, sizeof(head));
tot = 0;
memset(a,0,sizeof(a));
s = 0;
t = n + 1;
}
void add(int u, int v, int flow)
{
edge[tot].to = v;
edge[tot].flow = flow;
edge[tot].next = head[u];
head[u] = tot++;
}
bool bfs()
{
memset(dis,-1,sizeof(dis));
queue<int>q;
dis[s] = 0;q.push(s);
while(!q.empty())
{
int u = q.front();q.pop();
for(int i = head[u] ; i != -1;i = edge[i].next)
{
int v = edge[i].to;
if(dis[v] == -1 && edge[i].flow > 0)
{
dis[v] = dis[u] + 1;
if(v == t) return true;
q.push(v);
}
}
}
return false;
}
int dfs(int u,int flow_in)
{
if(u == t) return flow_in;
int flow_out = 0;
for(int i = cur[u] ; i != -1 ; i = edge[i].next)
{
cur[u] = i;
int v = edge[i].to;
if(dis[v] == dis[u] + 1 && edge[i].flow > 0)
{
int flow = dfs(v,min(flow_in,edge[i].flow));
if(flow == 0) continue;
flow_in -= flow;
flow_out += flow;
edge[i].flow -= flow;
edge[i^1].flow += flow;
if(flow_in == 0) break;
}
}
return flow_out;
}
int Dinic(int ans)
{
int sum = 0;
while(bfs())
{
for(int i = 0; i <= ans ;i ++)
cur[i] = head[i];
sum += dfs(s,inf);
}
return sum;
}
int main()
{
#ifdef LOCAL
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
init();
for (int i = 1, u, v, low, up; i <= m; i++)
{
scanf("%d%d%d%d", &u, &v, &low, &up);
in[i] = low; //该水管的初始流量，下界
a[u] -= low; //该点的流出量
a[v] += low; //该点的流入量
add(u,v,up-low);
add(v,u,0); //残余网络
id[i] = tot-1;
}
int s_out = 0; //记录s的流出量
for(int i = 1;i <= n ;i ++)
{
if(a[i] > 0)
add(s,i,a[i]),add(i,s,0),s_out += a[i];
else if(a[i] < 0)
add(i,t,-a[i]),add(t,i,0);
}
int max_flow = Dinic(n+1);
if(max_flow == s_out)
{
printf("YES\n");
for(int i = 1;i <= m ;i ++)
printf("%d\n",in[i] + edge[id[i]].flow); //加上反边的容量，即为该点相对于下界增加的流量
}
else
{
printf("NO\n");
}
}
return 0;
}
View Code