【题意】
给出一些边流量的上界和下界，问能否循环流通。
【思路】
黄学长讲得很清楚，直接贴过来：
【错误点】
忘记清空vector和in数组了orz
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define target n+1
using namespace std;
const int MAXM=+;
const int MAXN=+;
const int INF=0x7fffffff;
struct node
{
int to,pos,cap;
};
vector<node> E[MAXM];
int n,m,sum=;
int in[MAXN];
int dist[MAXN];
int low[MAXM];//记录下每条边的下界
int edge[MAXM][]; void addedge(int u,int v,int c)
{
E[u].push_back((node){v,E[v].size(),c});
E[v].push_back((node){u,E[u].size()-,});
} void init()
{
memset(in,,sizeof(in));//不要忘记了要清空in
for (int i=;i<target;i++) E[i].clear();//不要忘记了要清空vector
int u,v,c;
for (int i=;i<m;i++)
{
scanf("%d%d%d%d",&u,&v,&low[i],&c);
in[u]-=low[i];
in[v]+=low[i];
addedge(u,v,c-low[i]);
edge[i][]=v;
edge[i][]=E[v].size()-;
}
sum=;
for (int i=;i<=n;i++)
{
if (in[i]>)
{
addedge(,i,in[i]);
sum+=in[i];
}
else if (in[i]<) addedge(i,target,-in[i]);
}
} int bfs()
{
memset(dist,-,sizeof(dist));
queue<int> que;
while (!que.empty()) que.pop();
que.push();
dist[]=; while (!que.empty())
{
int head=que.front();
que.pop();
for (int i=; i<E[head].size(); i++)
{
node &tmp=E[head][i];
if (dist[tmp.to]==- && tmp.cap>)
{
dist[tmp.to]=dist[head]+;
que.push(tmp.to);
if (tmp.to==target) return ;
}
}
}
return ;
} int dfs(int s,int e,int maxflow)
{
int ret=;
if (s==e || maxflow==) return maxflow;
for (int i=;i<E[s].size();i++)
{
node &tmp=E[s][i];
if (dist[tmp.to]==dist[s]+ && tmp.cap>)
{
int delta=dfs(tmp.to,e,min(maxflow,tmp.cap));
if (delta>)
{
ret+=delta;
tmp.cap-=delta;
E[tmp.to][tmp.pos].cap+=delta;
maxflow-=delta;
}
}
}
return ret;
} void dinic()
{
int flow=;
while (bfs())
{
int f=dfs(,target,INF);
if (f>)
flow+=f;
else break;
}
if (flow!=sum) cout<<"NO"<<endl;
else
{
cout<<"YES"<<endl;
for (int i=;i<m;i++) cout<<low[i]+E[edge[i][]][edge[i][]].cap<<endl;
}
} int main()
{
while (~(scanf("%d%d",&n,&m)))
{
init();
dinic();
}
return ;
}