原题地址:https://nanti.jisuanke.com/t/39271
题意:给出n个物品,每个物品有一个权值,要求分成两份,使得两份的权值和最接近,并且有些物品之间有关系,表示不能 在同一份中,问你最后两份中较大的那份是权值和.
思路:由于限制条件,所以我们可以确定有些物品总是对立的,所以我们可以把对立的物品的差值放在背包里面进行dp,每个物品都可以取或不取,所以你都可以加上这个差值或者减去这个差值,我们进行一个可行性背包,找到第一个最小的差值就行了. 因为会出现负数,只需要加上一个大的数就行了.
#include <bits/stdc++.h> #define eps 1e-8 #define INF 0x3f3f3f3f #define PI acos(-1) #define lson l,mid,rt<<1 #define rson mid+1,r,(rt<<1)+1 #define CLR(x,y) memset((x),y,sizeof(x)) #define fuck(x) cerr << #x << "=" << x << endl using namespace std; typedef long long ll; typedef unsigned long long ull; const int seed = 131; const int maxn = 3e5 + 5; const int mod = 1e9 + 7; const int MX = 1.5e5 + 5; int T, n, m; int a[maxn]; struct node { int v, w, nxt; } e[maxn]; int tot, head[maxn]; void add_edge(int u, int v) { e[tot].v = v; e[tot].nxt = head[u]; head[u] = tot++; } vector<int>V; int vis[maxn]; vector<int>a1, a2; void dfs(int u, bool flag) { vis[u] = 1; if (flag) a1.push_back(u); else a2.push_back(u); for (int i = head[u]; ~i; i = e[i].nxt) { int v = e[i].v; if (vis[v]) continue; dfs(v, !flag); } } int dp[205][maxn];//dp[i][j]前i个物品,差值为j可不可行 int main() { scanf("%d", &T); while (T--) { tot = 0; V.clear(); CLR(vis, 0); CLR(head, -1); scanf("%d%d", &n, &m); int ret = 0; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); a[i] /= 100; ret += a[i]; } int num = ret; for (int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); add_edge(u, v); add_edge(v, u); } ret = 0; for (int i = 1; i <= n; i++) { if (!vis[i]) { a1.clear(); a2.clear(); dfs(i, 0); int sum1 = 0; int sum2 = 0; for (int i = 0; i < a1.size(); i++) { sum1 += a[a1[i]]; } for (int i = 0; i < a2.size(); i++) { sum2 += a[a2[i]]; } int x = abs(sum1 - sum2); ret += x; if (x != 0)V.push_back(x); } } int sz = V.size(); for (int i = 1; i <= sz; i++) { a[i] = V[i - 1]; } CLR(dp, 0); dp[0][MX] = 1; for (int i = 1; i <= sz; i++) { for (int j = -ret; j <= ret; j++) { if (dp[i - 1][j - a[i] + MX]) dp[i][j + MX] = 1; if (dp[i - 1][j + a[i] + MX]) dp[i][j + MX] = 1; } } for (int i = MX; i <= MX + ret; i++) { if (dp[sz][i]) { int x = i - MX; printf("%d\n", 100 * ((num - x) / 2 + x)); break; } } } return 0; } /* 10 4 1 300 300 100 500 1 2 300 6 4 1000 2000 1000 1500 1000 1500 1 2 2 3 4 5 5 6 */