- 1#include 2 3 using namespace std;
- 4 5#define inf 0x3f3f3f3f 6 7 const int maxn = 40010;
- 8 9 //int low[maxn],in[maxn],out[maxn];
- 10 11 struct Edge 12 {
- 13 int from,
- to,
- cap,
- flow;
- 14
- };
- 15 16 struct Dinic 17 {
- 18 int n,
- m,
- s,
- t;
- 19 vector edge;
- 20 vector < int > G[maxn];
- 21 bool vis[maxn];
- 22 int d[maxn];
- 23 int cur[maxn];
- 24 25 void init() 26 {
- 27
- for (int i = 0; i) 28 G[i].clear();
- 29 edge.clear();
- 30 memset(d, 0, sizeof(d));
- 31 memset(vis, 0, sizeof(vis));
- 32 memset(cur, 0, sizeof(cur));
- 33
- }
- 34 35 void AddEdge(int from, int to, int cap) 36 {
- 37 edge.push_back((Edge) {
- from,
- to,
- cap,
- 0
- });
- 38 edge.push_back((Edge) {
- to,
- from,
- 0,
- 0
- });
- 39 m = edge.size();
- 40 G[from].push_back(m - 2);
- 41 G[to].push_back(m - 1);
- 42
- }
- 43 44 bool BFS() 45 {
- 46 memset(vis, 0, sizeof(vis));
- 47 queue < int > Q;
- 48 Q.push(s);
- 49 d[s] = 0;
- 50 vis[s] = 1;
- 51
- while (!Q.empty()) 52 {
- 53 int x = Q.front();
- 54 Q.pop();
- 55
- for (int i = 0; i) 56 {
- 57 Edge & e = edge[G[x][i]];
- 58
- if (!vis[e.to] && e.cap > e.flow) 59 {
- 60 vis[e.to] = 1;
- 61 d[e.to] = d[x] + 1;
- 62 Q.push(e.to);
- 63
- }
- 64
- }
- 65
- }
- 66
- return vis[t];
- 67
- }
- 68 69 long long DFS(int x, int a) 70 {
- 71
- if (x == t || a == 0) return a;
- 72 long long flow = 0,
- f;
- 73
- for (int & i = cur[x]; i) 74 {
- 75 Edge & e = edge[G[x][i]];
- 76
- if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) 77 {
- 78 e.flow += f;
- 79 edge[G[x][i] ^ 1].flow -= f;
- 80 flow += f;
- 81 a -= f;
- 82
- if (a == 0) break;
- 83
- }
- 84
- }
- 85
- return flow;
- 86
- }
- 87 88 int Maxflow(int s, int t) {
- 89 this - >s = s;
- this - >t = t;
- 90 int flow = 0;
- 91
- while (BFS()) {
- 92 memset(cur, 0, sizeof(cur));
- 93 flow += DFS(s, inf);
- 94
- }
- 95
- return flow;
- 96
- }
- 97 98 void print(int cnt) {
- 99
- for (int i = 0; i) 100 printf("%d\n", edge[i * 2].flow + edge[G[0][i]].flow);
- 101
- }
- 102 103
- }
- sol;
- 104 105 106 int main() 107 {
- 108 int t;
- 109 scanf("%d", &t);
- 110
- while (t--) {
- 111 int n,
- m;
- 112 scanf("%d%d", &n, &m);
- 113 int low[maxn],
- uu[maxn],
- vv[maxn];
- 114 int sum = 0;
- 115 sol.init();
- 116
- for (int i = 0; i) {
- 117 int u,
- v,
- b,
- c;
- 118 scanf("%d%d%d%d", &u, &v, &b, &c);
- 119 low[i] = b;
- 120 uu[i] = u;
- 121 vv[i] = v;
- 122 sol.AddEdge(u, v, c - b);
- 123 sum += b;
- 124 // out[u] +=low[i];
- 125 // in[v] +=low[i];
- 126 // sol.AddEdge(0,v,b);
- 127 // sol.AddEdge(u,n+1,b);
- 128
- }
- 129 130
- for (int i = 0; i) {
- 131 sol.AddEdge(0, vv[i], low[i]);
- 132 sol.AddEdge(uu[i], n + 1, low[i]);
- 133
- }
- 134 135 int maxflow = sol.Maxflow(0, n + 1);
- 136
- if (sum != maxflow) 137 puts("NO");
- 138
- else {
- 139 puts("YES");
- 140 // for(int i=0;i<sol.G[0].size();i++) {
- 141 // printf("%d\n",sol.edge[sol.G[0][i]].flow);
- 142 // }
- 143 sol.print(m);
- 144
- }
- 145
- }
- 146
- return 0;
- 147
- }
来源: http://www.bubuko.com/infodetail-1989717.html