Loading... 把冲突关系合并成点，然后dp即可。 ```cpp #include <bits/stdc++.h> using namespace std; const int zero = 200 * 500; int dp[205][zero * 2 + 5]; vector<int> G[205]; int a[205]; bool vist[205]; vector<int> b; void dfs(int now, int & sum, int fh) { sum += fh * a[now]; vist[now] = true; for (auto & i: G[now]) { if (vist[i]) continue; dfs(i, sum, fh * -1); } } int main() { int T; scanf("%d",&T); while (T--) { memset(vist, false, sizeof(vist)); int n,m; scanf("%d%d",&n,&m); int SUM = 0; for (int i = 1; i <= n; i++) { scanf("%d",&a[i]); a[i] /= 100; SUM += a[i]; G[i].clear(); } for (int i = 1; i <= m; i++) { int u,v; scanf("%d%d",&u,&v); G[u].emplace_back(v); G[v].emplace_back(u); } b.clear(); int tot = 0; for (int i = 1; i <= n; i++) if (!vist[i]) { int sum = 0; dfs(i, sum, 1); sum = abs(sum); b.emplace_back(sum); tot += sum; } int N = (int)b.size(); memset(dp, 0, sizeof(dp)); dp[0][b[0] + zero] = dp[0][-b[0] + zero] = 1; for (int i = 1; i < N; i++) for (int j = zero - tot; j <= zero + tot; j++) { dp[i][j] |= (dp[i - 1][j - b[i]] | dp[i - 1][j + b[i]]); } for (int i = zero; i <= zero + tot; i++) if (dp[N - 1][i]) { printf("%d\n",(i - zero + SUM) * 50); break; } } return 0; } /* 1 4 2 1400 700 2100 900 1 3 3 4 */ ``` Last modification：May 29th, 2019 at 08:28 pm © 允许规范转载 Support If you think my article is useful to you, please feel free to appreciate ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
