班徽logo设计图片,网站优化排名的公司有哪些,江苏省和住房城乡建设厅网站首页,深圳企业倒闭1140 分珠 时间限制:500MS 内存限制:65536K提交次数:24 通过次数:18 题型: 编程题 语言: G;GCC Description 如下图所示#xff0c;有若干珠子#xff0c;每颗珠子重量不同#xff0c;珠子之间有一些细线将它们连在一起。现要求切断一些细线#xff0c;将它们分成两部分… 1140 分珠 时间限制:500MS 内存限制:65536K提交次数:24 通过次数:18 题型: 编程题 语言: G;GCC Description 如下图所示有若干珠子每颗珠子重量不同珠子之间有一些细线将它们连在一起。现要求切断一些细线将它们分成两部分
分割后单独每一部分的珠子仍保持相连且要求尽量做到两部分总重相等或相差最少。
请编一程序给定珠子个数、每颗珠子的重量以及珠子之间的连接情况输出按上述要求分割后两部分总重的差值的绝对值。输入格式 第一行有两个数N与M1N,M10N为珠子个数珠子编号依次为123...NM为连接珠子的细线数目。第二行为N个正整数分别为N个珠子的重量。此后M行每行两个数X与Y表示珠子X与珠子Y由细线相连。 输出格式 按要求分割后两部分总重的差值的绝对值。 输入样例 5 5
1 2 3 4 1
1 2
1 3
2 3
3 4
4 5输出样例 1 题解 dfs枚举出所有去掉某些边的情况。去掉边后用并查集求出此时有多少个联通块。如果正好有两个联通块则更新最小值 补充也可以dfs求联通块 #include iostream
#include cstdio
#include vector
#include algorithm
using namespace std;
typedef pair int,int pii;
const int maxn20;
pii P[maxn];
int n,m,cur,ans,val[maxn],flag[maxn],sum[maxn],M[maxn][maxn],f[maxn];
int find(int x)
{int rx,ix,t;while (r!f[r]) rf[r];while (i!r)//路径压缩{tf[i];f[i]r;it;}return r;
}
void mix(int x,int y)
{int fxfind(x),fyfind(y);if (fx!fy){f[fx]fy;sum[fy]sum[fx];//将儿子的值加给祖先cur--;//有两个块合并联通块数量减一}
}
void init()
{for (int i1;in;i)sum[i]val[i],f[i]i;curn;//联通块数量初始值为n
}
int getnum()
{init();for (int i0;im;i){if (flag[i])//该边没被取消mix(P[i].first,P[i].second);}if (cur2){for (int i2;in;i)if (find(i)!find(1))//此时只有两个联通块可以直接找出与1不是同一个祖先的return abs(sum[find(1)]-sum[find(i)]);}return -1;//联通块数量不为2
}
void dfs(int pos)
{if (posn1)return ;flag[pos]0;//取消该边int tempgetnum();if (temp-1)//得不到结果dfs(pos1);else ansmin(ans,temp);//得到了结果就没必要再取消这条边的情况下继续递归下去了直接更新flag[pos]1;dfs(pos1);//在不取消该边的情况下递归
}
int main()
{scanf(%d%d,n,m);ans0;for (int i1;in;i){scanf(%d,val[i]);ansval[i];}int a,b;for (int i0;im;i){scanf(%d%d,a,b);P[i]make_pair(a,b);flag[i]1;}dfs(1);printf(%d\n,ans);return 0;
} 转载于:https://www.cnblogs.com/scaugsh/p/5689814.html
