题意&＃xff1a;
有n个城市&＃xff0c;构成一棵树&＃xff0c;每个城市有v个人&＃xff0c;要求断开树上的一条边&＃xff0c;使得两个连通分量中的人数之差最小。问差的绝对值。&＃xff08;注意本题的M是没有用的&＃xff0c;因为所给的必定是一棵树&＃xff0c;边数M必定是n-1&＃xff09;
思路&＃xff1a;
考虑当前节点t&＃xff0c;当断开t与父亲的边时&＃xff0c;“子树t中的人数”与“剩下的人数”之差的绝对值若最小&＃xff0c;则为答案。
1 //#include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #define pii pair12 #define max(x,y) ((x)>(y)?(x):(y))13 #define min(x,y) ((x)<(y)?(x):(y))14 #define abs(x) ((x)<0?-(x):(x))15 #define INF 214748364716 #define LL long long17 using namespace std;18 const double PI &＃61; acos(-1.0);19 const int N&＃61;1000010;20 int edge_cnt, head[N], w[N];21 LL ans, sum;22 struct node23 {24 int from, to, next;25 node(){};26 node(int from,int to,int next):from(from),to(to),next(next){};27 }edge[N*2];28 29 void add_node(int from,int to)30 {31 edge[edge_cnt]&＃61;node(from,to,head[from]);32 head[from]&＃61;edge_cnt&＃43;&＃43;;33 }34 35 LL DFS(int t,int far) //枚举删除t头上的边36 {37 node e;38 LL cnt&＃61;0;39 for(int i&＃61;head[t]; i!&＃61;-1; i&＃61;e.next)40 {41 e&＃61;edge[i];42 if(e.to&＃61;&＃61;far) continue;43 cnt&＃43;&＃61;DFS(e.to, t);44 }45 cnt&＃43;&＃61;w[t]; //本子树的人数46 ans&＃61;min(ans, abs( 2*cnt-sum ));47 return cnt;48 }49 50 51 int main()52 {53 //freopen("input.txt", "r", stdin);54 int a, b, n, m, Case&＃61;0;55 while(scanf("%d%d",&n,&m), n&＃43;m)56 {57 sum&＃61;edge_cnt&＃61;0;58 memset(head,-1,sizeof(head));59 60 for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;)61 {62 scanf("%d",&w[i]);63 sum&＃43;&＃61;w[i];64 }65 ans&＃61;sum;66 for(int i&＃61;0; i)67 {68 scanf("%d%d",&a,&b);69 add_node(a,b);70 add_node(b,a);71 }72 DFS(1,-1);73 printf("Case %d: %lld\n", &＃43;&＃43;Case, ans);74 }75 return 0;76 }
转:https://www.cnblogs.com/xcw0754/p/4837659.html
![[大整数乘法] java代码实现](https://img1.php1.cn/3cd4a/24c6f/9f3/0133bb25da242824.jpeg)
京公网安备 11010802041100号