|
http://218.28.19.228:8081/cogs/index.php书架二题解
|
|
|
COGS 1825 [USACO Jan11]道路与航线由于 $T \leq 25000,R+P \leq 100000$ ，优先考虑SPFA，
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > v[25005];
int d[25005];
bool vis[25005];
int p[25005];
int T, R, P, S;
void SPFA(int s) {
memset(d, 0x3f, sizeof(d));
memset(vis, 0, sizeof(vis));
memset(p, 0, sizeof(p));
queue<int> q;
q.push(s);
vis[s] = true;
d[s] = 0;
while (!q.empty()) {
int x = q.front();
q.pop();
vis[x] = 0;
for (int i = 0; i < v[x].size(); i++) {
if (d[v[x][i].first] > d[x] + v[x][i].second) {
d[v[x][i].first] = d[x] + v[x][i].second, p[v[x][i].first] = x;
if (!vis[v[x][i].first]) q.push(v[x][i].first), vis[v[x][i].first] = true;
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> T >> R >> P >> S;
for (int i = 1; i <= R; i++) {
int a, b, c;
cin >> a >> b >> c;
v[a].push_back(make_pair(b, c));
v[b].push_back(make_pair(a, c));
}
for (int i = 1; i <= P; i++) {
int a, b, c;
cin >> a >> b >> c;
v[a].push_back(make_pair(b, c));
}
SPFA(S);
for (int i = 1; i <= T; i++) {
if (d[i] == 0x3f3f3f3f) cout << "NO PATH" << endl;
else cout << d[i] << endl;
}
return 0;
}
最终评测T两个点，考虑换方法。 查看资料注意到SPFA有双端队列优化和优先队列优化，优先队列复杂度 $O(logn)$，故不考虑。双端队列优化思路是：将要加入的节点与队头比较，小于等于插到队头，大于则插到队尾，时间复杂度接近 $O(1)$。 重写代码
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > v[25005];
int d[25005];
bool vis[25005];
int p[25005];
int T, R, P, S;
void SPFA(int s) {
memset(d, 0x3f, sizeof(d));
memset(vis, 0, sizeof(vis));
memset(p, 0, sizeof(p));
deque<int> q;
q.push_back(s);
vis[s] = true;
d[s] = 0;
while (!q.empty()) {
int x = q.front();
q.pop_front();
vis[x] = 0;
for (int i = 0; i < v[x].size(); i++) {
if (d[v[x][i].first] > d[x] + v[x][i].second) {
d[v[x][i].first] = d[x] + v[x][i].second, p[v[x][i].first] = x;
//主要改动如下
if (!vis[v[x][i].first]) {
if (d[v[x][i].first] <= d[q.front()]) q.push_front(v[x][i].first);
else q.push_back(v[x][i].first);
vis[v[x][i].first] = true;
}
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> T >> R >> P >> S;
for (int i = 1; i <= R; i++) {
int a, b, c;
cin >> a >> b >> c;
v[a].push_back(make_pair(b, c));
v[b].push_back(make_pair(a, c));
}
for (int i = 1; i <= P; i++) {
int a, b, c;
cin >> a >> b >> c;
v[a].push_back(make_pair(b, c));
}
SPFA(S);
for (int i = 1; i <= T; i++) {
if (d[i] == 0x3f3f3f3f) cout << "NO PATH" << endl;
else cout << d[i] << endl;
}
return 0;
}
后记在知乎上看到文章关于SPFA的各种优化以及对应hack，可以参考（如何看待 SPFA 算法已死这种说法？ - 知乎 (zhihu.com)）。
题目1825 [USACO Jan11]道路与航线
 2
评论
2025-07-01 10:55:47
|
|
|
Pro4034 罚站 题解
×
…提示!该题解未通过审核，建议分享者本着启发他人，照亮自己的初衷以图文并茂形式完善之，请勿粘贴代码。........................................................................ 该题解等待再次审核........................................................................(剩余 0 个中英字符)
题目4034 罚站
AAAAAAAAAA
2025-06-02 18:24:29
|
|
|
$题目大意$ ${求}\sum_{i=1}^{n}\sum _{j=1}^{m}{lcm(i,j)} {且} 1\le n,m\le 1e7$ ${正解:}$ ${有}{lcm(i,j)=\frac{i\cdot j}{\gcd(i,j)}}$ ${所以原式为:}$ $ans(n,m)=\sum_{i=1}^{n}\sum _{j=1}^{m}{\frac{i\cdot j}{\gcd(i,j)}}$ $~\qquad\qquad =\sum_{i=1}^{n}\sum _{j=1}^{m}{ \sum_{d\mid i,d\mid j,\gcd(\frac{i}{d},\frac{j}{d})}{}{\frac{i\cdot j}{d}}}$ ${现在需要将d给提出来,默认}{n\le m,}{我们设}i=i'\cdot d,j=j'\cdot d,{则}i'=\frac{i}{d},j'=\frac{j}{d},将i,j替换进上式得:$ $ans(n,m)=\sum_{d=1}^{\min(n,m)}{\sum_{i'=1}^{\left \lfloor \frac{n}{d} \right \rfloor}{\sum_{j'=1}^{\left \lfloor \frac{m}{d} \right \rfloor}{[\gcd(i',j')=1]\cdot d\cdot i'\cdot j'}}}$ $~\qquad\qquad=\sum_{d=1}^{n}{d\cdot\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}{\sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}{[\gcd(i,j)=1]\cdot i\cdot j}}}$ ${接着将d后面的部分再提出来考虑,化简枚举约数,运用莫比乌斯反演:} [\gcd(i,j)=1]=\sum_{d\mid gcd}{\mu{(d)}}:$ ${设} \ {g(n,m)}=\sum_{i=1}^{n}{\sum_{j=1}^{m}{[\gcd(i,j)=1]\cdot i\cdot j}}$ $~\qquad\qquad=\sum_{d=1}^{n}{\sum_{d\mid i}^{n}{\sum_{d\mid j}^{m}{\mu(d)\cdot i\cdot j}}}$ ${再设}\ i=i' \cdot d,j=j' \cdot d \ {带入,将}\mu{提出来}$ ${即}\ g(n,m)=\sum_{d=1}^{n}{\mu(d)}\cdot{d^{2}\cdot{\sum_{i=1}^{\left\lfloor \frac{n}{d} \right \rfloor}{\sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}{i\cdot j}}}}$ $~\qquad\qquad = \sum_{d=1}^{n}{\mu(d)}\cdot{d^{2}}\cdot\frac{{\left \lfloor \frac{n}{d} \right \rfloor}\cdot ({\left \lfloor \frac{n}{d} \right \rfloor}+1)\cdot {\left \lfloor \frac{m}{d} \right \rfloor}\cdot({\left \lfloor \frac{m}{d} \right \rfloor}+1)}{4}$ ${最后将g(n,m)带入ans(n,m)中得:}$ $ans(n,m)=\sum_{d=1}^{n}{d}\cdot{g(\left\lfloor \frac{n}{d}\right\rfloor,\left\lfloor \frac{m}{d}\right\rfloor)}$ ${用数论分块求出来}~{g(n,m)}~{再用数论分块求出来}~{ans(n,m),}~{就在{\Theta(n+m)内}}{得到答案了}~{(∠・ω< )⌒★}$
题目1886 [国家集训队 2011] Crash的数字表格
AAAAAAAAAAAAAAAAAAAA
4
1 条 评论
2025-05-24 21:56:25
|
|
|
Pro7 通信线路 题解通信线路 题解题目描述见 通信线路 整体思路只是一个最小生成树的模板题，数据量也没有很大 第一种方法：kruskal算法
两种实现：边集数组：时间复杂度$O(M log M + M(N + M))$； 第二种方法：Prim算法时间复杂度：$O(N^2)$（heap优化$O(M long M)$） 读者可以自行实现 代码实现最小生成树的两个主要算法都可以在讲义中找到，点击这个 本题解采用并查集 + kruskal 好孩子不可以抄代码哦 #include <bits/stdc++.h> // 万能头
using namespace std;
int n; // n是城市数
const int N = 1510,M = 1e4 + 10; // N是最大城市数，M是最大边数
struct Edge // 将边的参数定义到结构体里
{
int x,y,w; // x起点，y终点，w是权重
}e[M];
bool cmp(Edge &a,Edge &b) // 排序按照权重从小到大
{
return a.w < b.w;
}
int f[N]; // 并查集数组
void init()
{ // 并查集初始化
for(int i = 1; i <= N; ++i) f[i] = i;
}
int get(int x)
{ // 递归地查询x属于哪个集
if(x == f[x]) return x;
return f[x] = get(f[x]);
}
void merge(int x,int y)
{ // 将两个集合并
int fx = get(x),fy = get(y);
if(fx != fy) f[fy] = fx;
}
void kruskal()
{ // kruskal本体
init(); // 初始化
int ans = 0;
for(int i = 1;i <= M;i++)
{
int x = e[i].x,y = e[i].y,w = e[i].w; // 每次从边集中取出一个权重较小的
if(get(x) != get(y)) // 如果这条边的两个顶点不属于同一个集（就是不相连的意思）
{
merge(x,y); // 合并，即采用这条边
ans += w; // 总和记得加哦O(∩_∩)O
}
}
cout << ans << endl; // 输出就好乐，也可以返回ans在主函数里输出
}
int main()
{
freopen("mcst.in","r",stdin); // 文件输入输出
freopen("mcst.out","w",stdout);
cin >> n; // 输入城市数
int ind = 0;
for(int i = 0;i < n;i++)
{
for(int j = 0;j < n;j++)
{
int op; // 双重循环读入输入的矩阵（确信
cin >> op; // 第i+1个顶点到第j+1顶点之间边的权重
if(op != -1) e[ind].x = i + 1,e[ind].y = j + 1,e[ind].w = op,ind++;
// 如果两个顶点可以有边相连，就放在边集数组
}
}
sort(e,e+M,cmp); // 用cmp来排序
kruskal(); // kruskal，启动！
return 0; // 记得return是美德
}
|
|
|
×
提示!该题解未通过审核，建议分享者本着启发他人，照亮自己的初衷以图文并茂形式完善之，请勿粘贴代码。#include<iostream> using namespace std; int find(int x,int y,int n){ int num=x;
if(n-x+1<num) n 该题解等待再次审核........................................................................(剩余 790 个中英字符)
题目1811 [NOIP 2014PJ]螺旋矩阵
2025-05-10 07:27:49
|
