对于(u,v),
建立(u,v'),(v', u)容量都是1
(S,u)容量是d[u]
(u',T)容量是d[u]
跑网络流。过了。
#include <bits/stdc++.h> #define INF 0x7fffffff using namespace std; const int maxn = 105; const int maxm = 205; struct Edge { int from, to, cap, flow, next; Edge(int x=0, int y=0, int c=0, int nex=0) : from(x), to(y), cap(c), next(nex) { flow = 0; } }edges[100000]; int d[maxn], n, m, sum; int first[maxn + maxm], cur[maxn + maxm], tots; int S, T; void addEdge(int x, int y, int c) { edges[tots] = Edge(x, y, c, first[x]); first[x] = tots++; edges[tots] = Edge(y, x, 0, first[y]); first[y] = tots++; } bool vis[maxn+maxm]; int dep[maxn+maxm]; bool BFS() { memset(vis, 0, sizeof(vis)); queue<int> Q; Q.push(0); dep[0] = 0; vis[0] = 1; while (!Q.empty()) { int x = Q.front(); Q.pop(); for (int i = first[x]; i != -1; i = edges[i].next) { Edge &e = edges[i]; if (!vis[e.to] && e.cap > e.flow) { vis[e.to] = 1; dep[e.to] = dep[x] + 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 != -1; i = edges[i].next) { Edge &e = edges[i]; if (dep[x]+1 == dep[e.to] && (f = DFS(e.to, min(a, e.cap-e.flow))) > 0) { e.flow += f; edges[i^1].flow -= f; flow += f; a -= f; if (a == 0) break; } } return flow; } int main() { while (cin >> n >> m) { sum = 0; tots = 0; memset(first, -1, sizeof(first)); for (int i = 1; i <= n; ++i) { cin >> d[i]; sum += d[i]; } S = 0; T = 2*n + 1; for (int i = 1; i <= n; ++i) addEdge(S, i, d[i]); for (int i = 0; i < m; ++i) { int x, y; cin >> x >> y; addEdge(x, y+n, 1); addEdge(y, x+n, 1); } for (int i = n+1; i <= 2*n; ++i) addEdge(i, T, d[i-n]); int flow = 0; while (BFS()) { for (int i = S; i <= T; ++i) cur[i] = first[i]; flow += DFS(S, INF); } if (flow == sum) printf("Yes\n"); else printf("No\n"); } return 0; }
全部评论
(3) 回帖