无源无汇上下界网络流基础题。。。。先把上下界转化成一般的网络流形式,然后用流量平衡建图即可。。。
#include <iostream> #include <queue> #include <stack> #include <map> #include <set> #include <bitset> #include <cstdio> #include <algorithm> #include <cstring> #include <climits> #include <cstdlib> #include <cmath> #include <time.h> #define maxn 405 #define maxm 400005 #define eps 1e-10 #define mod 1000000007 #define INF 999999999 #define PI (acos(-1.0)) #define lowbit(x) (x&(-x)) #define mp make_pair #define ls o<<1 #define rs o<<1 | 1 #define lson o<<1,L,mid #define rson o<<1 | 1,mid+1,R #define pii pair<int,int> #pragma comment(linker,"/STACK:16777216") typedef long long LL; typedef unsigned long long ULL; //typedef int LL; using namespace std; LL qpow(LL a,LL b){LL res=1,base=a;while(b){if(b%2)res=res*base;base=base*base;b/=2;}return res;} LL powmod(LL a,base=a;while(b){if(b%2)res=res*base%mod;base=base*base%mod;b/=2;}return res;} // head struct Edge { int v,c,next; Edge() {} Edge(int v,int c,int next) : v(v),c(c),next(next) {} }E[maxm]; queue<int> q; int H[maxn],cntE; int dis[maxn]; int cur[maxn]; int cnt[maxn]; int pre[maxn]; int in[maxn]; int du[maxn]; int out[maxn]; int pipes[maxm]; int flow,s,t,nv,n,m,res; void addedges(int u,int v,int c) { E[cntE] = Edge(v,H[u]); H[u] = cntE++; E[cntE] = Edge(u,H[v]); H[v] = cntE++; } void bfs() { memset(cnt,sizeof cnt); memset(dis,-1,sizeof dis); cnt[0] = 1,dis[t] = 0; q.push(t); while(!q.empty()) { int u = q.front(); q.pop(); for(int e = H[u]; ~e; e = E[e].next) { int v = E[e].v; if(dis[v] == -1) { dis[v] = dis[u] + 1; cnt[dis[v]]++; q.push(v); } } } } int isap() { memcpy(cur,H,sizeof cur); flow = 0; bfs(); int u = pre[s] = s,e,minv,f,pos; while(dis[s] < nv) { if(u == t) { f = INF; for(int i = s; i != t; i = E[cur[i]].v) if(E[cur[i]].c < f) { f = E[cur[i]].c; pos = i; } for(int i = s; i != t; i = E[cur[i]].v) { E[cur[i]].c -= f; E[cur[i] ^ 1].c += f; } flow += f; u = pos; } for(e = H[u]; ~e; e = E[e].next) if(E[e].c && dis[E[e].v] + 1 == dis[u]) break; if(~e) { cur[u] = e; pre[E[e].v] = u; u = E[e].v; } else { if(--cnt[dis[u]] == 0) break; for(e = H[u],minv = nv; ~e; e = E[e].next) if(E[e].c && minv > dis[E[e].v]) { minv = dis[E[e].v]; cur[u] = e; } dis[u] = minv + 1; cnt[dis[u]]++; u = pre[u]; } } return flow; } void init() { res = cntE = 0; memset(H,sizeof H); memset(in,sizeof in); memset(du,sizeof du); memset(out,sizeof out); } void read() { int u,v,a,b; for(int i = 0; i < m; i++) { scanf("%d%d%d%d",&u,&v,&a,&b); int c = b - a; in[v] += a; out[u] += a; pipes[i] = a; addedges(u,c); } } void work() { s = 0,t = n + 1,nv = t + 1; for(int i = 1; i <= n; i++) { du[i] = in[i] - out[i]; if(du[i] > 0) addedges(s,i,du[i]),res += du[i]; else addedges(i,-du[i]); } if(isap() == res) { printf("YES\n"); for(int i = 0; i < m; i++) printf("%d\n",E[i * 2 + 1].c + pipes[i]); } else printf("NO\n"); } int main() { while(scanf("%d%d",&n,&m)!=EOF) { init(); read(); work(); } return 0; }