The 2019 ICPC Asia Shanghai Regional Contest H Tree Partition k、Color Graph

H题意：

给你一个n个节点n-1条无向边构成的树，每一个节点有一个权值wi，你需要把这棵树划分成k个子树，每一个子树的权值是这棵子树上所有节点权值之和。

你要输出这k棵子树的权值中那个最大的。你需要让输出的结果尽可能小

题解：

二分结果，重要的是判断这个二分的值是否满足题目要求

对于划分子树的选择，就选择子树中权值最大且又满足二分的答案的那个子树

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 2e5 + 10;

const int INF = 0x3f3f3f3f;

const long long Max = 1e14 + 10;

int n, k, cnt, flag, head[maxn], num;

ll w[maxn], sum[maxn];

struct Edge

{

    int v, nex;

} e[maxn << 2];

void add_edge(int x, int y)

{

    e[cnt].v = y;

    e[cnt].nex = head[x];

    head[x] = cnt++;

}

void dfs(int x, int fa, ll limit)

{

    sum[x] = w[x];

    for (int i = head[x]; ~i; i = e[i].nex)

    {

        if (!flag)

            return;

        int v = e[i].v;

        if (v != fa)

        {

            dfs(v, x, limit);

            sum[x] += sum[v];

        }

    }

    if (!flag)

        return;

    if (sum[x] > limit)

    {

        vector<ll> vec;

        for (int i = head[x]; ~i; i = e[i].nex)

        {

            int v = e[i].v;

            if (v != fa)

                vec.push_back(sum[v]);

        }

        sort(vec.begin(), vec.end());

        //int len=vec.size();

        while (sum[x] > limit)

        {

            // sum[x]-=vec[len-1];

            // num++;

            // vec.pop_back();

            // len--;

            sum[x] -= vec.back();

            vec.pop_back();

            num++;

        }

        vec.clear();

    }

    if (num > k - 1) //因为我们没有把vec清空，所以最后还需要num数量还需要加1

    {

        flag = 0;

        return;

    }

}

bool check(ll x)

{

    flag = 1;

    num = 0;

    dfs(1, 0, x);

    if (flag)

        return 1;

    else

        return 0;

}

int main()

{

    int t, p = 0;

    scanf("%d", &t);

    while (t--)

    {

        cnt = 0;

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

        memset(sum, 0, sizeof(sum));

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

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

        {

            int x, y;

            scanf("%d%d", &x, &y);

            add_edge(x, y);

            add_edge(y, x);

        }

        ll l = 1, r = Max, mid, ans;

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

        {

            scanf("%lld", &w[i]);

            l = max(l, w[i]);

        }

        while (l <= r)

        {

            mid = (l + r) >> 1;

            if (check(mid))

            {

                r = mid - 1;

                ans = mid;

            }

            else

            {

                l = mid + 1;

            }

        }

        printf("Case #%d: %lld\n", ++p, ans);

    }

    return 0;

}

K题意：

给你一个由n个节点m条边构成的一个无向图。保证不会出现重边和自环。你需要给边染色，你需要保证给一些边染色之后，图里面不会出现一个奇数环且这个环的所有边都被染色了。问你最多能给多少边染色。

题解：

就是二分图的一个性质。

你把这n个点分成两个集合（这一点暴力枚举就可以了，毕竟n<=16），然后如果一条边的两个端点在一个集合就不给它染色，否则就染色

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 10 + 10;

const int INF = 0x3f3f3f3f;

struct shudui

{

    int x, y;

} e[1000];

int main()

{

    int t, p = 0;

    scanf("%d", &t);

    while (t--)

    {

        int n, m;

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

        for (int i = 1; i <= m; ++i)

        {

            int x, y;

            scanf("%d%d", &x, &y);

            x -= 1;

            y -= 1;

            e[i].x = x;

            e[i].y = y;

        }

        int sum = 0;

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

        //for (int i = 7; i <= 7; ++i)

        {

            int res = 0;

            for (int j = 1; j <= m; ++j)

            {

                int x = e[j].x;

                int y = e[j].y;

                //printf("%d %d %d %d\n", x, y, ((1 << x) & i), ((1 << y) & i));

                if ((((1 << x) & i) > 0 && ((1 << y) & i) == 0) || (((1 << x) & i) == 0 && ((1 << y) & i) > 0))

                {

                    res++;

                }

            }

            // if (res == 5)

            // {

            //     printf("%d***\n", i);

            // }

            sum = max(sum, res);

        }

        printf("Case #%d: %d\n", ++p, sum);

    }

    return 0;

}

巴特西

The 2019 ICPC Asia Shanghai Regional Contest H Tree Partition k、Color Graph

最新文章

热门文章