1 /*  2     题意：无源无汇，并且每条边的容量有上下界限的网络流问题！既然无源无汇，那么素有的节点都应该满足“入流==出流”！  3          输出每一条边的流量，使得满足上面的条件。（如果u->v有流量，那么v->u就不会有流量）  4   5     思路：如果增加了源点s和汇点t，对于u->v（下限为l， 上限为f） 将这一条边拆成3条，s->v(容量为l)， u->v(容量为f-l)  6      u->t(容量为l)这样就变成了每一个点的流入或者流出的流量至少是b！然后从s->t走一遍最大流，如果所有的附件边都已经  7      满载，则就是所有s->v的边和u->t的边（或者只判断其中一者就可以），那么就存在答案！  8 */  9 #include<iostream> 10 #include<cstdio> 11 #include<cstring> 12 #include<algorithm> 13 #include<vector> 14 #include<queue> 15 #define INF 0x3f3f3f3f 16 #define N 205 17 #define M 500000 18 using namespace std; 19  20 struct EDGE{ 21     int v, cap, tot, nt, b; 22     EDGE(){}; 23     EDGE(int v, int cap, int nt, int b) : v(v), cap(cap), nt(nt), b(b), tot(cap){} 24 }; 25  26 EDGE edge[M]; 27 int n, m; 28 int first[N]; 29 int pre[N], d[N]; 30 int sz; 31 int s, t; 32 int full, fout;  33  34 void addEdge(int u, int v, int b, int cap){ 35     edge[sz] = (EDGE(v, cap, first[u],b)); 36     first[u] = sz++; 37     edge[sz] = (EDGE(u, 0, first[v], 0)); 38     first[v] = sz++; 39  40     edge[sz] = (EDGE(v, b, first[s], 0)); 41     first[s] = sz++; 42     edge[sz] = (EDGE(s, 0, first[v], 0)); 43     first[v] = sz++; 44  45     edge[sz] = (EDGE(t, b, first[u], 0)); 46     full += b; 47     first[u] = sz++; 48     edge[sz] = (EDGE(u, 0, first[t], 0)); 49     first[t] = sz++; 50 } 51  52 bool bfs(){ 53     queue<int>q; 54     memset(d, 0, sizeof(d)); 55     d[s] = 1; 56     q.push(s); 57     while(!q.empty()){ 58         int u = q.front(); q.pop(); 59         for(int i = first[u]; ~i; i = edge[i].nt){ 60             int v = edge[i].v; 61             if(!d[v] && edge[i].cap >0){ 62                 d[v] = d[u] + 1; 63                 q.push(v); 64             } 65         } 66     } 67     if(d[t] == 0) return false; 68     return true; 69 } 70  71 int dfs(int u, int totf){ 72     int ff; 73     if( u == t) return totf; 74     int flow = 0; 75     for(int i = first[u]; ~i && totf > flow; i = edge[i].nt){ 76         int v = edge[i].v; 77         int cap = edge[i].cap; 78         //流入u节点的当前总的流量为totf，可以得到 u->v1, u->v2, u->v3....这些路径上的最大流的和为flow+=f（u->vi） 79         //f(u->vi)表示u节点沿着vi节点方向的路径上的最大流；如果u->vi+1的容量为wi+1，那么u->vi+1所允许流过的最大 80         //的流量就是 min(totf - cost, wi+1)了！ 81         if(d[v] == d[u] + 1 && cap > 0 ){ 82             ff = dfs(v, min(totf - flow, cap)); 83             if(ff){ 84                 edge[i].cap -= ff; 85                 edge[i^1].cap += ff; 86                 flow += ff; 87             } 88             else 89                 d[v] = -1;//表示v这个点无法在继续增广下去了 90         } 91     } 92     return flow;//返回从u节点向外流出的最大流量！ 93 } 94  95 bool Dinic(){ 96     while(bfs()) 97         fout += dfs(0, INF);//这一块没想到写成while（dfs（））会超时.... 98  99     if( fout != full) return false;100     return true;101 }102 103 int main(){104      105         scanf("%d%d", &n, &m);106     memset(first, -1, sizeof(first));107     sz = 0;108     fout = full = 0;109     s = 0; t = n+1;110     int u, v, l, f;111     for(int i = 1; i <= m; ++i){112         scanf("%d%d%d%d", &u, &v, &l, &f);113         addEdge(u, v, l, f-l);114     }115     if(!Dinic()){116         printf("NO\n");117         return 0;118     }119     printf("YES\n");120     for(int i = 1; i <= m; ++i){121         int j = (i-1)*6;122         printf("%d\n",  edge[j].tot - edge[j].cap + edge[j].b);//输出这条边实际流过的流量+下限123     }124 125     return 0;126 }