题意：n个点m条边的图，有点权和边权，两个人轮流选点染色，每个人的得分为点权和加上所选点之间的边权和，问两人都最优策略时先手得分减去后手得分
边权分成两半，分别加到两个端点上，若两点同色则为一人得分，不同色则对两人得分贡献相同，计算得分差可以抵消
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #include<vector> 7 8 using namespace std; 9 10 const int MAXN = 11000; 11 int n, m; 12 double w[MAXN]; 13 14 template <typename tn> void read (tn & a) { 15 tn x = 0, f = 1; 16 char c = getchar(); 17 while (c < ‘0‘ || c > ‘9‘){ if (c == ‘-‘) f = -1; c = getchar(); } 18 while (c >= ‘0‘ && c <= ‘9‘){ x = x * 10 + c - ‘0‘; c = getchar(); } 19 a = f == 1 ? x : -x; 20 } 21 22 int main() { 23 read(n); 24 read(m); 25 for (int i = 1; i <= n; ++i) read(w[i]); 26 while (m--) { 27 int u, v; 28 double l; 29 read(u); 30 read(v); 31 read(l); 32 l /= (double) 2; 33 w[u] += l; 34 w[v] += l; 35 } 36 sort(w + 1, w + 1 + n); 37 double x = 0, y = 0; 38 for (int i = n; i > 0; i -= 2) { 39 x += w[i]; 40 y += w[i - 1]; 41 } 42 x -= y; 43 printf("%.0f\n", x); 44 return 0; 45 }
原文：https://www.cnblogs.com/m-m-m/p/8810352.html
