学习别人的方法。大致是：
无源汇的最大流 ： 新建源点，汇点，sum[i]为每个点进来的下界流之和减去出去的下界流之和，如果sum[i] > 0，由源点向该点建一条边，上界为sum[i]，下界为0
如果sum[i] < 0,由该点向汇点建边，上界为-sum[i]，下界为0。
跑一遍源点到汇点的最大流，当所有源点连得边都满流的时候存在可行流，当前的流量即为最大流。
#include <cstdio> #include <ctime> #include <cstdlib> #include <cstring> #include <queue> #include <string> #include <set> #include <stack> #include <map> #include <cmath> #include <vector> #include <iostream> #include <algorithm> #include <bitset> #include <fstream> using namespace std; //LOOP #define FF(i,a,b) for(int i = (a); i < (b); ++i) #define FE(i,b) for(int i = (a); i <= (b); ++i) #define FED(i,b,a) for(int i = (b); i>= (a); --i) #define REP(i,N) for(int i = 0; i < (N); ++i) #define CLR(A,value) memset(A,value,sizeof(A)) #define FC(it,c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++) //OTHER #define SZ(V) (int)V.size() #define PB push_back #define MP make_pair #define all(x) (x).begin(),(x).end() //INPUT #define RI(n) scanf("%d",&n) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&m,&k) #define RIV(n,k,p) scanf("%d%d%d%d",&k,&p) #define RV(n,p,q) scanf("%d%d%d%d%d",&p,&q) #define RS(s) scanf("%s",s) //OUTPUT #define WI(n) printf("%d\n",n) #define WS(n) printf("%s\n",n) //debug //#define online_judge #ifndef online_judge #define dt(a) << (#a) << "=" << a << " " #define debugI(a) cout dt(a) << endl #define debugII(a,b) cout dt(a) dt(b) << endl #define debugIII(a,c) cout dt(a) dt(b) dt(c) << endl #define debugIV(a,c,d) cout dt(a) dt(b) dt(c) dt(d) << endl #define debugV(a,d,e) cout dt(a) dt(b) dt(c) dt(d) dt(e) << endl #else #define debugI(v) #define debugII(a,b) #define debugIII(a,c) #define debugIV(a,d) #endif #define sqr(x) (x) * (x) typedef long long LL; typedef unsigned long long ULL; typedef vector <int> VI; const double eps = 1e-9; const int MOD = 1000000007; const double PI = acos(-1.0); const int INF = 0x3f3f3f3f; const int maxn = 100010; struct Edge{ int from,to,cap,flow,lcap; }; int n,s,t; vector<Edge> edges; VI G[maxn]; bool vis[maxn]; int d[maxn],cur[maxn]; void init() { REP(i,n + 1) G[i].clear(); edges.clear(); } void addEdge(int from,int to,int cap,int lcap) { edges.PB((Edge){from,lcap}); edges.PB((Edge){to,from,-lcap}); m = edges.size(); G[from].PB(m - 2); G[to].PB(m - 1); } bool bfs() { CLR(vis,0); queue<int> Q; Q.push(s); d[s] = 0,vis[s] = 1; while (!Q.empty()) { int u = Q.front(); Q.pop(); REP(i,G[u].size()) { Edge& e = edges[G[u][i]]; if (!vis[e.to] && e.cap > e.flow) { vis[e.to] = 1; d[e.to] = d[u] + 1; Q.push(e.to); } } } return vis[t]; } int dfs(int x,int a) { if (x == t || a == 0) return a; int flow = 0,f; for (int& i = cur[x];i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if (d[x] + 1 == d[e.to] && (f = dfs(e.to,min(a,e.cap - e.flow))) > 0) { e.flow += f; edges[G[x][i] ^ 1].flow -= f; flow += f; a -= f; if (a == 0) break; } } return flow; } int maxflow(int ss,int tt) { s = ss,t = tt; int flow = 0; while (bfs()) { CLR(cur,0); flow += dfs(s,INF); } return flow; } int sum[maxn]; int main() { //freopen("0.txt","r",stdin); int nodenum,edgenum; int u,v,l,c; int se,te; while (~RII(nodenum,edgenum)) { CLR(sum,0); n = nodenum + 2; init(); REP(i,edgenum) { RIV(u,c); addEdge(u,c - l,l); sum[u] -= l; sum[v] += l; } se = edges.size(),te = se; FE(i,1,nodenum) if (sum[i] > 0) addEdge(0,i,sum[i],0),te = edges.size(); FE(i,nodenum) if (sum[i] < 0) addEdge(i,nodenum + 1,-sum[i],0); int maxf = maxflow(0,nodenum + 1); // debugI(maxf); // debugII(se,te); bool f = 0; for (int i = se; i < te; i += 2) if (edges[i].flow < edges[i].cap) { f = 1; break; } if (f) puts("NO"); else { puts("YES"); // REP(i,edges.size()) for (int i = 0; i < se; i += 2) printf("%d\n",edges[i].flow + edges[i].lcap); } } return 0; }
