code:
#include <bits/stdc++.h>
using namespace std;
const int N = 210;
const int M = 1e4 + 200 + N, INF = 0x7f7f7f7f;
int n, m, s, t;
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
//链式前向星与建图
struct node {
int to, next, mival, val;
} a[N];
int pre[N], tot = 1;
void add (int u, int v, int mi, int ma) {
a[++ tot] = {v, pre[u], mi, ma - mi};
pre[u] = tot;
a[++ tot] = {u, pre[v], 0, 0};
pre[v] = tot;
}
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
int d[N], now[N], he[N];
int f[N];
bool bfs(){
memset(d, -1, sizeof(d));
queue<int>q;
q.push (s);
d[s] = 1;
now[s] = pre[s];
while (!q.empty()){
int p = q.front();
q.pop();
for (int i = pre[p]; i; i = a[i].next){
int to = a[i].to;
if (a[i].val && d[to] == -1){
d[to] = d[p] + 1;
now[to] = pre[to];
if(to == t)return 1;
q.push (to);
}
}
}
return 0;
}
int find(int x, int lim){
if (x == t) return lim;
int flow = 0;
for(int i = now[x]; i && flow < lim; i = a[i].next){
now[x] = i;
int to = a[i].to;
if (d[to] == d[x] + 1 && a[i].val){
int t = find(to, min(a[i].val, lim-flow));
if (!t) d[to] = -1;
a[i].val -= t;
a[i ^ 1].val +=t;
flow +=t;
}
}
return flow;
}
int dinic(){
int flow, res=0;
while (bfs()){
while (1){
flow = find (s, INF);
if (flow == 0) break;
res += flow;
}
}
return res;
}
int main () {
cin >> n >> m;
s = 0, t = n + 1;
for (int i = 1; i <= m; i ++) {
int x, y, l, r;
cin >> x >> y >> l >> r;
add (x, y, l, r);
he[x] -= l;
he[y] += l;
}
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (he[i] > 0) add (s, i, 0, he[i]), cnt += he[i];
else if (he[i] < 0) add (i, t, 0, -he[i]);
}
if (dinic() != cnt) puts ("NO");
else {
puts ("YES");
for(int i = 2; i <= m * 2 + 1; i += 2)
cout<<a[i ^ 1].val + a[i].mival<<'\n';
}
return 0;
}
其中now为当前弧优化