1 条题解
-
1
#include <cstdio> #include <cstring> #include <iostream> #include <queue> using namespace std; const int N = 2e2 + 5, M = 2e4 + 5, INF = 1e9; int n, m, s, t, w[N], ans[M]; int idx = 1, h[N]; struct edge { int to, nxt, val; } e[M << 1]; void addEdge(int u, int v, int c) { e[++idx] = (edge) { v, h[u], c }; h[u] = idx; } int dep[N], now[N]; queue <int> q; bool BFS() { memset(dep, 0, sizeof(dep)); while (!q.empty()) q.pop(); dep[s] = 1, q.push(s); now[s] = h[s]; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = h[u]; i; i = e[i].nxt) { int v = e[i].to; if (!e[i].val || dep[v]) continue; q.push(v), dep[v] = dep[u] + 1, now[v] = h[v]; if (v == t) return true; } } return false; } int DFS(int u, int sum) { if (u == t) return sum; int res = 0; for (int &i = now[u]; i && sum; i = e[i].nxt) { int v = e[i].to; if (dep[v] != dep[u] + 1 || !e[i].val) continue; int k = DFS(v, min(sum, e[i].val)); e[i].val -= k, e[i ^ 1].val += k; ans[i >> 1] += ((i & 1) ? -1 : 1) * k; sum -= k, res += k; } return res; } bool dinic() { bool flag = true; while (BFS()) DFS(s, INF); for (int i = (m << 1) + 2; i <= idx; i += 2) flag &= !e[i].val; return flag; } int main() { scanf("%d%d", &n, &m), t = n + 1; for (int i = 1, u, v, l, r; i <= m; i++) scanf("%d%d%d%d", &u, &v, &l, &r), w[u] -= l, w[v] += l, ans[i] = l, addEdge(u, v, r - l), addEdge(v, u, 0); for (int i = 1; i <= n; i++) if (w[i] > 0) addEdge(s, i, w[i]), addEdge(i, s, 0); else if (w[i] < 0) addEdge(i, t, -w[i]), addEdge(t, i, 0); if (!dinic()) return puts("NO") & 0; puts("YES"); for (int i = 1; i <= m; i++) printf("%d\n", ans[i]); return puts("") & 0; }
- 1
信息
- ID
- 5546
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者