传送门：https://nanti.jisuanke.com/t/39271

题意：

给你n个人，每个人有一个权值 a_i ，（a_i是可以被100整除的)）现在需要你将n个人分成两组，有m个关系，a和b有关系代表a和b不能放在同一个组内，为了两组实力尽量平均，要你求两组权值差值最小时最大的值是哪一个

题解：

二分图染色+dp

首先我们知道n个人必须全选分为两组，其次题目保证有解

因此我们很容易想到如果a->b,b->c，那么a一定和c要分在同一组内

这样我们就得到了很多个联通块

错误想法：我们得到了num个联通块后直接将num个联通块做01背包就可以求出差值最小时最大值，dp状态定义为前i个物品，容量为j时的最大值，但是实际上这样有可能把错误的情况考虑进来，例如两个矛盾的块同时放进一个背包，例如这组数据

2

4 1

300 300 100 500

1 2

6 4

1000 2000 1000 1500 1000 1500

1 2

2 3

4 5

5 6

01背包得到的答案是600 和 4000，实际上应该是 800和5000

正确想法，我们将物品分成联通块后，对分成的两个联通块做差值，之后枚举差值能否达到才是最优解，为了防止差值为负，我们在中间加上一个比较大的数即可

代码：

错误写法：

#include <set>

#include <map>

#include <deque>

#include <queue>

#include <stack>

#include <cmath>

#include <ctime>

#include <bitset>

#include <cstdio>

#include <string>

#include <vector>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

typedef long long ll;

typedef pair<LL, LL> pLL;

typedef pair<LL, int> pLi;

typedef pair<int, LL> pil;;

typedef pair<int, int> pii;

typedef unsigned long long uLL;

#define ls rt<<1

#define rs rt<<1|1

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define bug printf("*********\n")

#define FIN freopen("input.txt","r",stdin);

#define FON freopen("output.txt","w+",stdout);

#define IO ios::sync_with_stdio(false),cin.tie(0)

#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"

#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"

#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"

const double eps = 1e-8;

const int mod = 1e9 + 7;

const int maxn = 2e5 + 5;

const int INF = 0x3f3f3f3f;

const LL INFLL = 0x3f3f3f3f3f3f3f3f;

struct EDGE {

    int v, nxt;

} edge[maxn << 1];

int head[maxn], tot;

void add_edge(int u, int v) {

    edge[tot].v = v;

    edge[tot].nxt = head[u];

    head[u] = tot++;

}

int a[maxn];

int num[maxn];

int num1, num2;

int vis[maxn];

int dp[205][maxn];

void dfs(int u, int flag) {

    vis[u] = 1;

    if(flag) num1 += a[u];

    else num2 += a[u];

    for(int i = head[u]; i != -1; i = edge[i].nxt) {

        int v = edge[i].v;

        if(vis[v]) continue;

        dfs(v, !flag);

    }

}

int main() {

#ifndef ONLINE_JUDGE

    FIN

#endif

    int T;

    scanf("%d", &T);

    while(T--) {

        int n, m;

        memset(head, -1, sizeof(head));

        tot = 0;

        int cur = 0;

        int sum = 0, ret;

        memset(vis, 0, sizeof(vis));

        memset(num, 0, sizeof(num));

        scanf("%d%d", &n, &m);

        for(int i = 1; i <= n; i++) {

            scanf("%d", &a[i]);

            a[i] /= 100;

            sum += a[i];

        }

        ret = sum / 2;

        for(int i = 1, u, v; i <= m; i++) {

            scanf("%d%d", &u, &v);

            add_edge(u, v);

            add_edge(v, u);

        }

        for(int i = 1; i <= n; i++) {

            if(!vis[i]) {

                num1 = 0, num2 = 0;

                dfs(i, 0);

                if(num1 != 0) {

                    num[++cur] = num1;

                }

                if(num2 != 0) {

                    num[++cur] = num2;

                }

            }

        }

        memset(dp, 0, sizeof(dp));

        for(int i = 1; i <= cur; i++) {

            for(int j = 0; j <= ret; j++) {

                dp[i][j] = dp[i - 1][j];

                if(j >= num[i])dp[i][j] = max(dp[i][j], dp[i - 1][j - num[i]] + num[i]);

            }

        }

        printf("%d\n", (sum - dp[cur][ret]) * 100);

    }

    return 0;

}

正确写法：

#include <set>

#include <map>

#include <deque>

#include <queue>

#include <stack>

#include <cmath>

#include <ctime>

#include <bitset>

#include <cstdio>

#include <string>

#include <vector>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

typedef long long ll;

typedef pair<LL, LL> pLL;

typedef pair<LL, int> pLi;

typedef pair<int, LL> pil;;

typedef pair<int, int> pii;

typedef unsigned long long uLL;

#define ls rt<<1

#define rs rt<<1|1

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define bug printf("*********\n")

#define FIN freopen("input.txt","r",stdin);

#define FON freopen("output.txt","w+",stdout);

#define IO ios::sync_with_stdio(false),cin.tie(0)

#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"

#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"

#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"

const double eps = 1e-8;

const int mod = 1e9 + 7;

const int maxn = 2e5 + 5;

const int INF = 0x3f3f3f3f;

const LL INFLL = 0x3f3f3f3f3f3f3f3f;

struct EDGE {

    int v, nxt;

} edge[maxn << 1];

int head[maxn], tot;

void add_edge(int u, int v) {

    edge[tot].v = v;

    edge[tot].nxt = head[u];

    head[u] = tot++;

}

int a[maxn];

int num[maxn];

int num1, num2;

int vis[maxn];

int dp[205][maxn];

void dfs(int u, int flag) {

    vis[u] = 1;

    if(flag) num1 += a[u];

    else num2 += a[u];

    for(int i = head[u]; i != -1; i = edge[i].nxt) {

        int v = edge[i].v;

        if(vis[v]) continue;

        dfs(v, !flag);

    }

}

int main() {

#ifndef ONLINE_JUDGE

    FIN

#endif

    int T;

    scanf("%d", &T);

    while(T--) {

        int n, m;

        memset(head, -1, sizeof(head));

        tot = 0;

        int cur = 0;

        int sum = 0, ret;

        memset(vis, 0, sizeof(vis));

        memset(num, 0, sizeof(num));

        scanf("%d%d", &n, &m);

        for(int i = 1; i <= n; i++) {

            scanf("%d", &a[i]);

            a[i] /= 100;

            sum += a[i];

        }

        for(int i = 1, u, v; i <= m; i++) {

            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]) {

                num1 = 0, num2 = 0;

                dfs(i, 0);

                num[++cur] += abs (num1 - num2);

                ret += abs(num1 - num2);

            }

        }

        memset(dp, 0, sizeof(dp));

        dp[0][100000] = 1;

        for (int i = 1; i <= cur; i++) {

            for (int j = -ret; j <= ret; j++) {

                if (dp[i - 1][j - num[i] + 100000]) dp[i][j + 100000] = 1;

                if (dp[i - 1][j + num[i] + 100000]) dp[i][j + 100000] = 1;

            }

        }

        for (int i = 100000; i <= 100000 + ret; i++) {

            if (dp[cur][i]) {

                int x = i - 100000;

                printf("%d\n", 100 * ((sum - x) / 2 + x));

                break;

            }

        }

    }

    return 0;

}

巴特西

2019 ICPC 陕西西安邀请赛 D. Miku and Generals

题意：

题解：

代码：

最新文章

热门文章