xzm2019

2019 西安邀请赛D Miku and Generals
把冲突关系合并成点,然后dp即可。#include <bits/stdc++.h> using nam...
扫描右侧二维码阅读全文
29
2019/05

2019 西安邀请赛D Miku and Generals

把冲突关系合并成点,然后dp即可。

#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
If you think my article is useful to you, please feel free to appreciate

Leave a Comment