P6815 [PA2009] Cakes 题目分析
分析题目性质
本质上是求三个点组成的环的点权最大值的和。
思路
暴力
考虑枚举第一个点 \(i\)，然后枚举与其相邻的第二个点 \(j\)，用 \(set\) 存储 \(i,j\) 相连的点，最后判断得出答案。
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
#include <vector>
#include <set>
#define N 100005
#define int long long
using namespace std;
int n,m,a[N],ans;
vector<int> g[N];
signed main(){
cin >> n >> m;
for (int i = 1;i <= n;i ++) cin >> a[i];
for (int i = 1;i <= m;i ++) {
int x,y;
cin >> x >> y;
g[x].push_back(y),g[y].push_back(x);
}
for (int i = 1;i <= n;i ++)
for (auto nxt1 : g[i]) {
set<int> st1,st2;
for (auto j : g[i])
if (j != nxt1)st1.insert(j);
for (auto j : g[nxt1])
if (j != i) st2.insert(j);
for (auto j : st1)
if (st2.find(j) != st2.end() && i < nxt1 && nxt1 < j)
ans += max(max(a[j],a[nxt1]),a[i]);
}
cout << ans;
return 0;
}
考虑完全图，上述代码会跑得很慢，得分 \(28\) 分。
完全图时，时间复杂度为 \(\mathcal{O}(n^3\log n).\)
建图优化
我们发现满足答案的满足 \(i<j<k\) 这种情况。
观察我们枚举的顺序：不难得出当前点 \(x\) 相连的点 \(y\) 必须满足 \(x<y\)。换言之，我们可以在建图的时候只使小的点连向大的点。
具体代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
#include <vector>
#include <set>
#define N 100005
#define int long long
using namespace std;
int n,m,a[N],ans;
vector<int> g[N];
signed main(){
cin >> n >> m;
for (int i = 1;i <= n;i ++) cin >> a[i];
for (int i = 1;i <= m;i ++) {
int x,y;
cin >> x >> y;
if (x > y) swap(x,y);
g[x].push_back(y);
}
for (int i = 1;i <= n;i ++)
for (auto nxt1 : g[i]) {
set<int> st1,st2;
for (auto j : g[i])
if (j != nxt1)st1.insert(j);
for (auto j : g[nxt1])
if (j != i) st2.insert(j);
for (auto j : st1)
if (st2.find(j) != st2.end())
ans += max(max(a[j],a[nxt1]),a[i]);
}
cout << ans;
return 0;
}
得分 \(86\) 分，是一个客观分数。
考虑什么时候最慢：一条链的时候节点枚举为 \((n-1)(n-2)+(n-2)(n-3)\dots+ 2\times1.\)
所以说：时间复杂度是 \(\mathcal{O}(n^2\log n)\) 的。
枚举第三个点优化
我们不需要用 \(set\) 去判断，而是用一个 \(vis\) 数组去标记。
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
#include <vector>
#include <set>
#define N 100005
#define int long long
using namespace std;
int n,m,a[N],ans;
vector<int> g[N];
bool vis[N];
signed main(){
cin >> n >> m;
for (int i = 1;i <= n;i ++) cin >> a[i];
for (int i = 1;i <= m;i ++) {
int x,y;
cin >> x >> y;
if (x > y) swap(x,y);
g[x].push_back(y);
}
for (int i = 1;i <= n;i ++) {
for (auto j : g[i]) vis[j] = 1;
for (auto j : g[i])
for (auto k : g[j])
if (vis[k]) ans += max(max(a[i],a[j]),a[k]);
for (auto j : g[i])
vis[j] = 0;
}
cout << ans;
return 0;
}
得分 \(100\) 分，非正解。
还是考虑链的情况，时间复杂度为 \(\mathcal{O}(n^2).\)
至于怎么过去的我也不知道，还望加强数据。
度数建图优化
用度数大的去连接度数小的点，度数一样的用编号小的连接大的。
我们发现，这一些点的出度似乎是处于一个比较平衡的状态，其实不然，这个状态不大于 \(\sqrt m.\)
时间复杂度 \(\mathcal{O}(m\sqrt m).\)
可得 \(100\) 分。
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
#include <vector>
#include <set>
#define N 100005
#define M 300005
#define int long long
using namespace std;
int n,m,a[N],ans;
vector<int> g[N];
bool vis[N];
int d[N];
struct node{
int x,y;
}in[M];
signed main(){
cin >> n >> m;
for (int i = 1;i <= n;i ++) cin >> a[i];
for (int i = 1;i <= m;i ++) cin >> in[i].x >> in[i].y,d[in[i].x] ++,d[in[i].y] ++;
for (int i = 1;i <= m;i ++) {
int x = in[i].x,y = in[i].y;
if (d[x] < d[y] || (d[x] == d[y] && x > y)) swap(x,y);
g[x].push_back(y);
}
for (int i = 1;i <= n;i ++) {
for (auto j : g[i]) vis[j] = 1;
for (auto j : g[i])
for (auto k : g[j])
if (vis[k]) ans += max(max(a[i],a[j]),a[k]);
for (auto j : g[i])
vis[j] = 0;
}
cout << ans;
return 0;
}