D. Miku and Generals-蒲公英云

D. Miku and Generals

题目链接//nanti.jisuanke.com/t/39271
本题是要你进行选取，使得两个部分的差值最小，然后输入最大的那个值。
通过x+y=sum x-y=mul。我们可以知道，只要我们求出差值，就可以的到题目所要值。
故本题转换为通过选取得到两个部分，使得差值最小，求最小差值。
本题唯一限制点在于部分数据是对立的。
我们可以把所有对立的数据通过01染色得到染色为0和染色为1的点的差值。
同时，如果没有对立点的情况下，那差值就是他本身。这样，我们就可以得到，选取每个部分，对整体所产生的差值影响了。
每个部分所产生差值影响，我们得到了。那么，我们就可以使用可行性背包，得到最小差值。同时，注意到差值可能为负，所以，我们运用小技巧，把dp[0][MX]当成差值为0的地方。这样负值也可以表示出来了。

#include"string.h"
#include"vector"
#include"algorithm"
using namespace std;
const int N = 300;
const int MX = 1.5e5 + 5;
const int maxn = 3e5 + 5;
int T,n,m;
int a[N],b[N];
vector<int> G[N];
int vis[N],sum1,sum2;
int dp[205][maxn];
int num;
void dfs(int x,int flag)
{
    vis[x] = 1;
    if(flag == 0) sum1 += a[x];
    else sum2 += a[x];
    for(int i = 0; i < G[x].size(); i ++)
    {
        if(vis[G[x][i]] == 0)
        {
            dfs(G[x][i],!flag);
        }
    }
}
int main()
{
    scanf("%d",&T);
    while(T --)
    {
        scanf("%d%d",&n,&m);
        num = 0;
        for(int i = 1; i <= n; i ++)
        {
            vis[i] = 0; G[i].clear();
            scanf("%d",&a[i]);
            a[i] /= 100; num += a[i];
        }
        for(int i = 1; i <= m; i ++)
        {
            int u,v; scanf("%d%d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        int ret = 0;
        int top = 0;
        for(int i = 1; i <= n; i ++)
        {
            if(vis[i] == 0)
            {
                sum1 = sum2 = 0;
                dfs(i,0);
                int mul = abs(sum1 - sum2);
                ret += mul;
                if(mul != 0)
                b[++ top] = mul;
            }
        }
        memset(dp,0,sizeof(dp));
        dp[0][MX] = 1;
        for(int i = 1; i <= top; i ++)
        {
            for(int j = -ret; j <= ret; j ++)
            {
                if(dp[i - 1][j - b[i] + MX]) dp[i][j + MX] = 1;
                if(dp[i - 1][j + b[i] + MX]) dp[i][j + MX] = 1;
            }
        }
        int loc = 0;
        for(int i = MX; i <= MX + ret; i ++)
        if(dp[top][i]) {
            loc = i - MX; break;
        }
        printf("%d\n",100 * ((num + loc) / 2));
    }
}