{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e .sampledata { font-family: \"Courier New\", Courier, monospace; white-space: pre; }\u003c/style\u003e\u003cdiv style\u003d\"background: white\" align\u003d\"left\"\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e 阿狸和桃子正在玩一个游戏,游戏是在一个带权图\u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003eG\u003d(V, E)\u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e上进行的,设节点权值为\u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003ew(v)\u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e,边权为\u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003ec(e)\u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e。游戏规则是这样的:\u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e\u003cbr\u003e \u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e \u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e1. \u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e阿狸和桃子轮流将图中的顶点染色,阿狸会将顶点染成红色,桃子会将顶点染成粉色。已经被染过色的点不能再染了,而且每一轮都必须给一个且仅一个顶点染色。\u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e\u003cbr\u003e \u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e \u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e2. \u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e为了保证公平性,节点的个数\u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003eN\u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e为偶数。\u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e\u003cbr\u003e \u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e \u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e3. \u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e经过\u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003eN/2\u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e轮游戏之后,两人都得到了一个顶点集合。对于顶点集合\u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003eS\u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e,得分计算方式为\u003cimg height\u003d\"71\" width\u003d\"266\" alt\u003d\"\" SRC\u003d\"CDN_BASE_URL/00bf443cdd06a5135b71750948b44fb2?v\u003d1591683440\"\u003e\u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e\u003cbr\u003e \u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e \u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e。\u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e\u003cbr\u003e \u003c/span\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e 由于阿狸石头剪子布输给了桃子,所以桃子先染色。两人都想要使自己的分数比对方多,且多得越多越好。如果两人都是采用最优策略的,求最终桃子的分数减去阿狸的分数。\u003c/span\u003e\n\u003c/div\u003e \n\u003cdiv style\u003d\"background: white\" align\u003d\"left\"\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e \u003c/span\u003e\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e\u003cfont size\u003d\"3\"\u003e\u003cfont color\u003d\"#200000\"\u003e 输入第一行包含两个正整数\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003eN\u003c/span\u003e\u003c/font\u003e\u003c/font\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e和\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003eM\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e,分别表示图\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003eG\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e的节点数和边数,保证\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003eN\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e一定是偶数。\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e\u003cbr\u003e \u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e 接下来\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003eN+M\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e行。\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e\u003cbr\u003e \u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e 前\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003eN\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e行,每行一个整数\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003ew\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e,其中第\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003ek\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e行为节点\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003ek\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e的权值。\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e\u003cbr\u003e \u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e 后\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003eM\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e行,每行三个用空格隔开的整数\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003ea b c\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e,表示一条连接节点\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003ea\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e和节点\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003eb\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e的边,权值为\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003ec\u003c/span\u003e\u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e。\u003c/span\u003e\u003c/p\u003e \n\u003cdiv style\u003d\"background: white\" align\u003d\"left\"\u003e\n \u003cspan style\u003d\"font-size: 12pt; color: #200000\"\u003e \u003c/span\u003e\n\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e\u003cfont color\u003d\"#200000\" size\u003d\"3\"\u003e 输出仅包含一个整数,为桃子的得分减去阿狸的得分。\u003c/font\u003e\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cspan class\u003dsampledata\u003e4 4\r\n6\r\n4\r\n-1\r\n-2\r\n1 2 1\r\n2 3 6\r\n3 4 3\r\n1 4 5\r\n\u003c/span\u003e\u003c/div\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cspan class\u003dsampledata\u003e3\r\n数据规模和约定\r\n 对于40%的数据,1 ≤ N ≤ 16。\r\n 对于100%的数据,1 ≤ N ≤ 10000,1 ≤ M ≤ 100000,-10000 ≤ w , c ≤ 10000。\r\n \u003c/span\u003e\u003c/div\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cp\u003e\u003c/p\u003e"}}]}