虽然,以前就看过上下界这套理论,,但是一直没去过题。。今天终于补上了。。。
无源汇上下界网络流,,记录一下每个点流出去的下界流和流进来的下界流,,,如果IN>OUT,所以,,需要补上IN-OUT的自由流量才能在去掉下界之后保持流量平衡
反之,需要流掉OUT-IN的流量才能保持流量平衡
#include<algorithm> #include<iostream> #include<cstring> #include<queue> #include<cstdio> using namespace std; #define mem(x,y) memset(x,y,sizeof(x)) #define FIN freopen("input.txt","r",stdin) #define fuck(x) cout<<x<<endl const int MX=111111; #define INF 0x3f3f3f3f #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 int n,m; int s,t; int head[MX],cnt; int low[2*MX]; int IN[MX],OUT[MX]; struct Edge { int nxt,to,cap; } E[2*MX]; void edge_init() { mem(head,-1); cnt=0; } void edge_add(int u,int v,int cap) { E[cnt].nxt=head[u]; E[cnt].to=v; E[cnt].cap=cap; head[u]=cnt++; } bool vis[MX]; int d[MX],cur[MX]; bool BFS(int s,int t) { mem(vis,0); queue<int> Q; Q.push(s); vis[s]=1; d[s]=0; d[t]=-1; while(!Q.empty()) { int u=Q.front(); Q.pop(); for(int i=head[u]; ~i; i=E[i].nxt) { int v=E[i].to; if(vis[v]||!E[i].cap) continue; d[v]=d[u]+1; vis[v]=1; Q.push(v); } } return d[t]!=-1; } int DFS(int x,int t,int a) { if(x==t||a==0) return a; int flow=0,f; for(int &i=cur[x]; ~i; i=E[i].nxt) { int v=E[i].to; if(d[v]==d[x]+1&&(f=DFS(v,t,min(a,E[i].cap)))) { E[i].cap-=f; E[i^1].cap+=f; flow+=f; a-=f; if(a==0) break; } } return flow; } int Dinic(int s,int t) { int flow=0; while(BFS(s,t)) { memcpy(cur,head,sizeof(head)); flow+=DFS(s,INF); } return flow; } int main() { FIN; int T; while(cin>>T) { while(T--) { edge_init(); mem(IN,0); mem(OUT,0); scanf("%d%d",&n,&m); s=0; t=n+1; for(int i=0; i<m; i++) { int u,v,l,r; scanf("%d%d%d%d",&u,&v,&l,&r); low[i]=l; IN[v]+=l; OUT[u]+=l; edge_add(u,r-l); edge_add(v,u,0); } int sum=0; for(int i=1; i<=n; i++) { if(IN[i]>OUT[i]) edge_add(s,i,IN[i]-OUT[i]),edge_add(i,s,0),sum+=IN[i]-OUT[i]; if(IN[i]<OUT[i]) edge_add(i,OUT[i]-IN[i]),edge_add(t,0); } if(sum==Dinic(s,t)) { puts("YES"); for(int i=0; i<m; i++) { printf("%d\n",E[2*i+1].cap+low[i]); } } else puts("NO\n"); } } return 0; }