无源无汇上下界网络流裸题
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <cmath> #include <queue> #include <vector> using namespace std; #define N 210 #define INF 1000000000 int n,m,S,T,Ans; struct Edge{ int to,next; int value; }edge[N*N*2]; int head[N],tot=1; int dis[N],cur[N],Free[N],low[N*N]; queue<int> Q; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x*f; } void Addedge(int u,int v,int w) { tot++;edge[tot].next=head[u];edge[tot].value=w;edge[tot].to=v;head[u]=tot; tot++;edge[tot].next=head[v];edge[tot].value=0;edge[tot].to=u;head[v]=tot; } bool BFS() { memset(dis,-1,sizeof(dis)); dis[S]=0;Q.push(S); while(!Q.empty()) { int now=Q.front();Q.pop(); for(int i=head[now];i;i=edge[i].next) { int v=edge[i].to; if(dis[v]<0&&edge[i].value>0) { dis[v]=dis[now]+1; Q.push(v); } } } return dis[T]>0; } int Find(int k,int low) { if(k==T) return low; int qwer; for(int i=cur[k];i;i=edge[i].next) { cur[k]=i; int v=edge[i].to; if(dis[v]==dis[k]+1&&edge[i].value>0&&(qwer=Find(v,min(low,edge[i].value)))) { edge[i].value-=qwer; edge[i^1].value+=qwer; return qwer; } } return 0; } void Dinic() { while(BFS()) { for(int i=0;i<=T;i++) cur[i]=head[i]; while(1) { int qwer=Find(S,INF); if(qwer==0) break; Ans+=qwer; } } } bool Pd() { for(int i=head[S];i;i=edge[i].next) { if(edge[i].value) return false; } return true; } int main() { int Case=read(); while(Case--) { tot=1; memset(head,sizeof(head)); memset(Free,sizeof(Free)); n=read();m=read(); S=0;T=n+1; for(int i=1;i<=m;i++) { int x=read(),y=read();low[i]=read();int z=read(); Free[x]-=low[i];Free[y]+=low[i]; Addedge(x,y,z-low[i]); } for(int i=1;i<=n;i++) { if(Free[i]>0) Addedge(S,i,Free[i]); else Addedge(i,-Free[i]); } Ans=0;Dinic(); if(Pd()) { printf("YES\n"); for(int i=1;i<=m;i++) { printf("%d\n",edge[i*2+1].value+low[i]); } } else printf("NO\n"); } return 0; }