数据结构算法求边权和【数学 | 模拟】

题目链接

题目描述：

初始给出一个 n 个点顺次连接而成的环，点有点权，边权是两个端点的点权乘积。现在给出一些特殊点，这些特殊点是向其他所有点都有连边，如果连边时发现两点之间已经有边，不会再次连接（即图中不会有重边）。求图中边权和。

---

做法1（模拟）：

首先我们先将这个环边的权值累加到答案中，然后求特殊点产生的权值和，我们令sum等于所有点的权值和，对于第一个特殊点 x，它的贡献为a[x] * sum - (a[x] - 相邻点的权值)，因为不会有重边，也就是说每个边只能产生一次贡献，此时 x 连的边都已经贡献完了，所以此时将 x 从 sum 中减去，并用done数据进行标记，所以在前面说的减去“相邻点的权值”时，要先看他它是不是已经被标记了，若被标记就不用再减了。

---

做法2（数学）：

a，b，c三个数互相相乘一次转换为多项式，2ab + 2ac + 2bc = (a + b + c) * (a + b + c) - (a * a + b * b + c * c)，多个数类似，所以互相乘一次的结果为右式除以2。
所以先假设所有点都是特殊点，然后求出总的边权和，然后减去非特殊点为被假设为特殊点时的总的边权和，此时可能环上的边被减去了，所以最后要加回来。

---

做法1 AC Codes：

#include <iostream> #include <vector> #include <queue> #include <stack> #include <set> #include <map> //#include <unordered_set> //#include <unordered_map> #include <deque> #include <list> #include <iomanip> #include <algorithm> #include <fstream> #include <cmath> #include <cstdio> #include <cstring> #include <cstdlib> //#pragma GCC optimize(2) using namespace std; typedef long long ll; //cout << fixed << setprecision(2); //cout << setw(2); const int N = 2e5 + 6, M = 1e9 + 7, INF = 0x3f3f3f3f; int main() { //freopen("/Users/xumingfei/Desktop/ACM/test.txt", "r", stdin); ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int n; cin >> n; vector<int> a(n), b(n), done(n); ll sum = 0; for (int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; } ll ans = 0; for (int i = 0; i < n; i++) { ans += a[i] * a[(i + 1) % n]; } for (int i = 0; i < n; i++) { cin >> b[i]; if (b[i]) { ll now = sum - a[i]; if (!done[(i + 1) % n]) now -= a[(i + 1) % n]; if (!done[(i - 1 + n) % n]) now -= a[(i -1 + n) % n]; ans += a[i] * now; sum -= a[i]; done[i] = 1; } } cout << ans << '\n'; return 0; } 

做法2 AC Codes：

 #include <iostream> #include <vector> #include <queue> #include <stack> #include <set> #include <map> //#include <unordered_set> //#include <unordered_map> #include <deque> #include <list> #include <iomanip> #include <algorithm> #include <fstream> #include <cmath> #include <cstdio> #include <cstring> #include <cstdlib> //#pragma GCC optimize(2) using namespace std; typedef long long ll; //cout << fixed << setprecision(2); //cout << setw(2); const int N = 2e5 + 6, M = 1e9 + 7, INF = 0x3f3f3f3f; int main() { //freopen("/Users/xumingfei/Desktop/ACM/test.txt", "r", stdin); ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int n; cin >> n; ll all = 0; vector<int> a(n), b(n); for (int i = 0; i < n; i++) { cin >> a[i]; all += a[i]; } ll ans = 0, sum = 0; for (int i = 0; i < n; i++) { cin >> b[i]; if (b[i]) { sum += a[i]; ans -= a[i] * a[i]; } } ans += sum * sum; ans /= 2; for (int i = 0; i < n; i++) { ans += a[i] * a[(i + 1) % n]; if (b[i]) ans += (all - sum) * a[i]; if (b[i] || (!b[i] && b[(i + 1) % n])) ans -= a[i] * a[(i + 1) % n]; } cout << ans << '\n'; return 0; } 

本文地址：https://blog.csdn.net/weixin_44258590/article/details/109031063