题目链接：http://acm.sgu.ru/problem.php?contest=0&problem=194

当所有附加边全部满流时（即maxflow==所有du[]>0之和），有可行解。

代码：

#include <iostream> @H_403_9@
#include <algorithm> @H_403_9@
#include <set> @H_403_9@
#include <map> @H_403_9@
#include <string.h> @H_403_9@
#include <queue> @H_403_9@
#include <sstream> @H_403_9@
#include <stdio.h> @H_403_9@
#include <math.h> @H_403_9@
#include <stdlib.h> @H_403_9@
#include <string>@H_403_9@

using@H_403_9@ namespace@H_403_9@ std@H_403_9@;

const@H_403_9@ int@H_403_9@ MAXN = 1010@H_403_9@;//点数的最大值@H_403_9@
const@H_403_9@ int@H_403_9@ MAXM = 400100@H_403_9@;//边数的最大值@H_403_9@
const@H_403_9@ int@H_403_9@ INF = 0x3f3f3f3f@H_403_9@;

struct@H_403_9@ Edge
{
    int@H_403_9@ to,next,cap,flow;
}edge[MAXM];//注意是MAXM@H_403_9@

int@H_403_9@ tol;
int@H_403_9@ head[MAXN];
int@H_403_9@ gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN];

void@H_403_9@ init()
{
    tol = 0@H_403_9@;
    memset@H_403_9@(head,-1@H_403_9@,sizeof@H_403_9@(head));
}
//加边，单向图三个参数，双向图四个参数@H_403_9@
void@H_403_9@ addedge(int@H_403_9@ u,int@H_403_9@ v,int@H_403_9@ w,int@H_403_9@ rw = 0@H_403_9@)
{
    edge[tol].to = v; edge[tol].cap = w; edge[tol].next = head[u];
    edge[tol].flow = 0@H_403_9@; head[u] = tol++;
    edge[tol].to = u; edge[tol].cap = rw; edge[tol].next = head[v];
    edge[tol].flow = 0@H_403_9@; head[v] = tol++;
}
//输入参数：起点、终点、点的总数@H_403_9@
//点的编号没有影响，只要输入点的总数@H_403_9@
int@H_403_9@ sap(int@H_403_9@ start,int@H_403_9@ end,int@H_403_9@ N)
{
    memset@H_403_9@(gap,0@H_403_9@,sizeof@H_403_9@(gap));
    memset@H_403_9@(dep,sizeof@H_403_9@(dep));
    memcpy@H_403_9@(cur,head,sizeof@H_403_9@(head));
    int@H_403_9@ u = start;
    pre[u] = -1@H_403_9@;
    gap[0@H_403_9@] = N;
    int@H_403_9@ ans = 0@H_403_9@;
    while@H_403_9@ (dep[start] < N)
    {
        if@H_403_9@ (u == end)
        {
            int@H_403_9@ Min = INF;
            for@H_403_9@ (int@H_403_9@ i = pre[u]; i != -1@H_403_9@; i = pre[edge[i ^ 1@H_403_9@].to])
                if@H_403_9@ (Min > edge[i].cap - edge[i].flow)
                    Min = edge[i].cap - edge[i].flow;
            for@H_403_9@ (int@H_403_9@ i = pre[u]; i != -1@H_403_9@; i = pre[edge[i ^ 1@H_403_9@].to])
            {
                edge[i].flow += Min;
                edge[i ^ 1@H_403_9@].flow -= Min;
            }
            u = start;
            ans += Min;
            continue@H_403_9@;
        }
        bool@H_403_9@ flag = false@H_403_9@;
        int@H_403_9@ v;
        for@H_403_9@ (int@H_403_9@ i = cur[u]; i != -1@H_403_9@; i = edge[i].next)
        {
            v = edge[i].to;
            if@H_403_9@ (edge[i].cap - edge[i].flow && dep[v] + 1@H_403_9@ == dep[u])
            {
                flag = true@H_403_9@;
                cur[u] = pre[v] = i;
                break@H_403_9@;
            }
        }
        if@H_403_9@ (flag)
        {
            u = v;
            continue@H_403_9@;
        }
        int@H_403_9@ Min = N;
        for@H_403_9@ (int@H_403_9@ i = head[u]; i != -1@H_403_9@; i = edge[i].next)
            if@H_403_9@ (edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)
            {
                Min = dep[edge[i].to];
                cur[u] = i;
            }
        gap[dep[u]]--;
        if@H_403_9@ (!gap[dep[u]])return@H_403_9@ ans;
        dep[u] = Min + 1@H_403_9@;
        gap[dep[u]]++;
        if@H_403_9@ (u != start) u = edge[pre[u] ^ 1@H_403_9@].to;
    }
    return@H_403_9@ ans;
}

int@H_403_9@ n,m;
int@H_403_9@ in[MAXN],least[MAXM],num[MAXM];

int@H_403_9@ main()
{
    while@H_403_9@ (~scanf@H_403_9@("%d%d"@H_403_9@,&n,&m))
    {
        init();
        memset@H_403_9@(in,sizeof@H_403_9@(in));
        memset@H_403_9@(least,sizeof@H_403_9@(least));

        int@H_403_9@ a,b,c,d;
        for@H_403_9@ (int@H_403_9@ i = 1@H_403_9@;i <= m;i++)
        {
            scanf@H_403_9@("%d%d%d%d"@H_403_9@,&a,&b,&c,&d);
            num[i] = tol;
            least[i] = c;
            in[a] -= c;
            in[b] += c;

            addedge(a,d - c);
        }
        int@H_403_9@ sum = 0@H_403_9@;
        for@H_403_9@ (int@H_403_9@ i = 1@H_403_9@;i <= n;i++)
        {
            if@H_403_9@ (in[i] > 0@H_403_9@)
            {
                addedge(0@H_403_9@,i,in[i]);
                sum += in[i];
            }
            else@H_403_9@ addedge(i,n + 1@H_403_9@,-in[i]);
        }
        if@H_403_9@ (sap(0@H_403_9@,n + 2@H_403_9@) != sum) puts@H_403_9@("NO"@H_403_9@);
        else@H_403_9@
        {
            puts@H_403_9@("YES"@H_403_9@);
            for@H_403_9@ (int@H_403_9@ i = 1@H_403_9@;i <= m;i++) printf@H_403_9@("%d\n"@H_403_9@,edge[num[i]].flow + least[i]);
        }

    }
    return@H_403_9@ 0@H_403_9@;
}