求一个无源无汇的有上下界的最大流。分析:
把每条边的边容量重设为上界-下界,记录每个点的最小进入in和最小输出流out,重设一个s、t,将s、t连向每一个点,边容量分别为每个点的in和out,从s到t跑最大流即
可。如果s的每条边满流,则有解,否则无解。
- #include <cstdio>
- #include <algorithm>
- #include <queue>
- using namespace std;
- const int MAXN = 209,INF = 1e9;
- int n,m;
- struct Edge
- {
- int v,ne;
- int f,c,l;
- }edge[MAXN*MAXN];
- int edgehead[MAXN],p = 1;
- int sum,in[MAXN],out[MAXN];
- int dis[MAXN];
- void add(int u,int v,int f,int l)
- {
- edge[p].v = v;edge[p].c = edge[p].f = f;edge[p].l = l;
- edge[p].ne = edgehead[u];edgehead[u] = p++;
- }
- int adv(int k) {return ((k-1)^1)+1;}
- bool bfs(int s,int t)
- {
- for(int i = 1; i <= n; ++i) dis[i] = INF;
- dis[t] = 0;
- queue<int> q;
- q.push(t);
- while(!q.empty())
- {
- int u = q.front();q.pop();
- for(int i = edgehead[u]; i; i = edge[i].ne)
- {
- int v = edge[i].v,f = edge[adv(i)].f;
- if(f && dis[v] > dis[u]+1)
- {
- dis[v] = dis[u]+1;
- q.push(v);
- }
- }
- }
- return dis[s] != INF;
- }
- int dfs(int now,int t,int flow)
- {
- if(now == t || flow == 0) return flow;
- int re = 0,tmp;
- for(int i = edgehead[now]; i; i = edge[i].ne)
- {
- int to = edge[i].v;
- if(dis[to] == dis[now]-1 && edge[i].f && (tmp = dfs(to,t,min(flow,edge[i].f))))
- {
- re += tmp;flow -= tmp;
- edge[i].f -= tmp;edge[adv(i)].f += tmp;
- if(flow == 0) break;
- }
- }
- dis[now] = INF;
- return re;
- }
- int dinic(int s,int maxf)
- {
- int re = 0;
- while(bfs(s,t))
- re += dfs(s,maxf);
- return re;
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i = 1; i <= m; ++i)
- {
- int a,b,d;
- scanf("%d%d%d%d",&a,&b,&c,&d);
- in[b] += c;out[a] += c;sum += c;
- add(a,d-c,c);
- add(b,a,0);
- }
- for(int i = 1; i <= n; ++i)
- {
- if(in[i]) add(n+1,i,in[i],0),add(i,n+1,0);
- if(out[i]) add(i,n+2,out[i],add(n+2,0);
- }
- n += 2;
- if(dinic(n-1,n,INF) != sum)
- {
- puts("NO");
- goto end;
- }
- puts("YES");
- for(int i = 1; i <= m; ++i)
- printf("%d\n",edge[2*i-1].c-edge[2*i-1].f+edge[2*i-1].l);
- end:;
- return 0;
- }