【题目分析】
无源汇上下界可行流。
上下界网络流的问题可以参考这里。↓
http://www.cnblogs.com/kane0526/archive/2013/04/05/3001108.html
【代码】
#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>//#include <map>#include <set>#include <queue>#include <string>#include <iostream>#include <algorithm>using namespace std;#define maxn 205#define me 50005#define inf 0x3f3f3f3f#define F(i,j,k) for (int i=j;i<=k;++i)#define D(i,j,k) for (int i=j;i>=k;--i)void Finout(){ #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin);// freopen("out.txt","w",stdout); #endif}int Getint(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();} while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f;}int h[me<<1],to[me<<1],ne[me<<1],fl[me<<1],en=0,S=0,T=me-1;int id[me<<1];void add(int a,int b,int c,int ID){//cout<<"add "<<a<<" "<<b<<" "<<c<<endl; to[en]=b; ne[en]=h[a]; fl[en]=c; id[en]=ID; h[a]=en++; to[en]=a; ne[en]=h[b]; fl[en]=0; id[en]=0; h[b]=en++;}int map[me];bool tell(){ queue <int> q; memset(map,-1,sizeof map); map[S]=0; while (!q.empty()) q.pop(); q.push(S); while (!q.empty()) { int x=q.front(); q.pop();// cout<<"bfs"<<x<<endl; for (int i=h[x];i>=0;i=ne[i]) {// cout<<"to "<<to[i]<<endl; if (map[to[i]]==-1&&fl[i]>0) { map[to[i]]=map[x]+1; q.push(to[i]); } } }// cout<<"over"<<endl; if (map[T]!=-1) return true; return false;}int zeng(int k,int r){ if (k==T) return r; int ret=0; for (int i=h[k];i>=0&&ret<r;i=ne[i]) if (map[to[i]]==map[k]+1&&fl[i]>0) { int tmp=zeng(to[i],min(fl[i],r-ret)); ret+=tmp; fl[i]-=tmp; fl[i^1]+=tmp; } if (!ret) map[k]=-1; return ret;}int ans[me<<1],n,m,du[me<<1],dn[me<<1];int main(){ Finout(); while (scanf("%d%d",&n,&m)!=EOF) { memset(h,-1,sizeof h); memset(ans,0,sizeof ans); memset(du,0,sizeof du); memset(dn,0,sizeof dn); F(i,1,m) { int a,b,c,d; a=Getint();b=Getint();c=Getint();d=Getint(); add(a,b,d-c,i); du[a]-=c; du[b]+=c; dn[i]+=c;}F(i,1,n){if (du[i]) add(S,i,du[i],0);if (du[i]<0) add(i,T,-du[i],0);}int now=0,tmp=0;while (tell()) while (tmp=zeng(S,inf)) now+=tmp;int flag=1;for (int i=h[S];i>=0;i=ne[i])if (fl[i]>0) flag=0;if (!flag) printf("NO\n");else{printf("YES\n");F(i,0,en-1) ans[id[i]]=fl[i^1];F(i,1,m) printf("%d\n",ans[i]+dn[i]);}}}
