无源汇上下界可行流

无源汇上下界可行流
首先把每条边设置为max-min
然后计算每个点如果流量守恒，还需要流入多少，或流出多少
最后根据这个流入和流出对S和T之间进行建图
最后边权就是min+流过的就可以了

//试一下
#include <bits/stdc++.h>
using namespace std;
const int N=305;
const int M=1e6+5;

int h[N],ne[M],e[M],w[M],tot=1;
void add(int from,int to,int wi) {
    e[++tot]=to;
    w[tot]=wi;
    ne[tot]=h[from];
    h[from]=tot;
}

int n,m,S,T;
int dep[N],gap[N];
void bfs() {
    dep[T]=1;
    queue<int>q;
    q.push(T);
    while(!q.empty()) {
        int now=q.front();
        q.pop();
        gap[dep[now]]++;
        for(int i=h[now];i;i=ne[i]) {
            int to=e[i];
            if(dep[to])continue;
            dep[to]=dep[now]+1;
            q.push(to);
        }
    }
}

int cur[N];
int dfs(int now,int sum) {
    if(now==T)return sum;
    int ans=0;
    for(int i=cur[now];i&&sum;i=ne[i]) {
        cur[now]=i;
        int to=e[i];
        if(w[i]>0&&dep[now]-1==dep[to]) {
            int k=dfs(to,min(sum,w[i]));
            w[i]-=k;
            w[i^1]+=k;
            sum-=k;
            ans+=k;
        }
    }
    if(sum==0)return ans;
    if(--gap[dep[now]]==0)dep[S]=n+3;
    gap[++dep[now]]++;
    return ans;
}

int ISAP() {
    int ans=0;
    bfs();
    while(dep[S]<=n+2) {
        memcpy(cur,h,sizeof(h));
        ans+=dfs(S,1e9);
    }
    return ans;
}

int a[M],b[M];

int main() {
    cin>>n>>m;
    S=n+1,T=n+2;
    int sum=0;
    for(int i=1;i<=m;i++) {
        int x,y,w1,w2;
        cin>>x>>y>>w1>>w2;
        add(x,y,w2-w1);
        add(y,x,0);
        a[x]+=w1;
        a[y]-=w1;
        b[i]=w1;//最小流量
    }
    for(int i=1;i<=n;i++) {
        if(a[i]>0)add(i,T,a[i]);
        else if(a[i]<0)add(S,i,-a[i]),sum-=a[i];
    }
    if(ISAP()==sum) {
        cout<<"YES\n";
        for(int i=2;i<=2*m;i+=2)
            cout<<b[i/2]+w[i^1]<<'\n';
    }
    else cout<<"NO\n";
    return 0;
}