本文主要是介绍Miku and Generals-西安邀请赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：https://nanti.jisuanke.com/t/39271
题意：给你n个权值 然你分成两组 使他们的权值和的差最小 ，其中有些点是相互矛盾的，不能分在同一组。
分析：所有点都是100的倍数，可以直接除以100，我们二分图染色，每个联通块只有两种情况，因为确定了一个点的所属集合，相邻点就都确定了，而且只有两个集合，然后dp记录所有组合构成的值，dp[i]表示当前这个差值能不能到达，这个过程可以通过可行性背包来解决。然后找一个最小的差值就可以了。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int dp[N],pre[N],c[210],vs[210],t,n,m,sum,s1,s2;
vector<int> e[210];void dfs(int u,int x) {vs[u]=1;if(x) s1+=c[u]/100;else s2+=c[u]/100;for(int i=0;i<e[u].size();i++) {int v=e[u][i];if(!vs[v]) dfs(v,x^1);}
}int main()
{while(~scanf("%d",&t)) {while(t--) {sum=0;memset(dp,0,sizeof(dp));memset(vs,0,sizeof(vs));scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) e[i].clear();for(int i=1;i<=n;i++) scanf("%d",&c[i]),sum+=c[i]/100;for(int i=1;i<=m;i++) {int u,v;scanf("%d%d",&u,&v);e[u].push_back(v);e[v].push_back(u);}dp[0]=1;for(int i=1;i<=n;i++) {s1=s2=0;if(vs[i]) continue;dfs(i,0);int ss=abs(s1-s2);for(int j=0;j<=sum;j++) {if(!dp[j]) continue;pre[j+ss]=1;if(j>=ss) pre[j-ss]=1;else pre[ss-j]=1;}for(int i=0;i<=sum;i++) dp[i]=pre[i],pre[i]=0;}int k=0;while(dp[++k]==0);printf("%d\n",50*(k+sum));}}return 0;
}
这篇关于Miku and Generals-西安邀请赛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
