D. Miku and Generals

ゝ一世哀愁。 2023-07-03 12:26 113阅读 0赞

题目链接:https://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));
        }
    }