网站 缓存方式,珠海百度关键字优化,济南58同城网,平台托管是什么意思题目背景
“咚咚咚……”“查水表#xff01;”原来是查水表来了#xff0c;现在哪里找这么热心上门的查表员啊#xff01;小明感动得热泪盈眶#xff0c;开起了门……
题目描述
妈妈下班回家#xff0c;街坊邻居说小明被一群陌生人强行押上了警车#xff01;妈妈丰富…题目背景
“咚咚咚……”“查水表”原来是查水表来了现在哪里找这么热心上门的查表员啊小明感动得热泪盈眶开起了门……
题目描述
妈妈下班回家街坊邻居说小明被一群陌生人强行押上了警车妈妈丰富的经验告诉她小明被带到了 tt 区而自己在 ss 区。
该市有 mm 条大道连接 nn 个区一条大道将两个区相连接每个大道有一个拥挤度。小明的妈妈虽然很着急但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 ss 至 tt 的路线使得经过道路的拥挤度最大值最小。
输入格式
第一行有四个用空格隔开的 nnmmsstt其含义见【题目描述】。
接下来 mm 行每行三个整数 u,v,wu,v,w表示有一条大道连接区 uu 和区 vv且拥挤度为 ww。
两个区之间可能存在多条大道。
输出格式
输出一行一个整数代表最大的拥挤度。
输入输出样例
输入 #1复制
3 3 1 3 1 2 2 2 3 1 1 3 3
输出 #1复制
2
说明/提示
数据规模与约定 对于 30% 的数据保证 n≤10。 30% n≤10 对于 60% 的数据保证 n≤100。 60% n≤100 对于 100% 的数据保证 1≤n≤1041≤m≤2×104w≤1041≤s,t≤n。且从 s 出发一定能到达 t 区。 100% 1≤n≤104 1≤m≤2×104 w≤104 1≤s,t≤n s t 样例输入输出 1 解释
小明的妈妈要从 11 号点去 33 号点最优路线为 11-22-33。
接上昨天邻接表的写法
kruskal的做法在昨天的总结中
源代码
#include iostream
#include algorithm
#include vector
using namespace std;
const int M 2e4 5;
int n, m, s, t;
int dist[M];
bool vis[M];
vectorpairint, int g[M];
int prim() {for (int i 1; i m; i) {dist[i] 1e9;}dist[s] 0;int MAX_min 0;for (int i 1; i m; i) {int p -1;for (int j 1; j m; j) {if (!vis[j] (p -1 || dist[p] dist[j]))p j;}if (dist[p] 1e9)return 1e9;vis[p] 1;MAX_min max(MAX_min, dist[p]);if (p t)return MAX_min;for (const auto edge : g[p]) {int to edge.first;int w edge.second;dist[to] min(dist[to], w);}}return -1;
}
int main() {cin n m s t;for (int i 1; i m; i) {int u, v, w;cin u v w;g[u].emplace_back(v, w);g[v].emplace_back(u, w);}int y prim();cout y;return 0;
}题目描述
又到了一年一度的明明生日了明明想要买 BB 样东西巧的是这 BB 样东西价格都是 AA 元。
但是商店老板说最近有促销活动也就是
如果你买了第 II 样东西再买第 JJ 样那么就可以只花 KI,JKI,J 元更巧的是KI,JKI,J 竟然等于 KJ,IKJ,I。
现在明明想知道他最少要花多少钱。
输入格式
第一行两个整数A,BA,B。
接下来 BB 行每行 BB 个数第 II 行第 JJ 个为 KI,JKI,J。
我们保证 KI,JKJ,IKI,JKJ,I 并且 KI,I0KI,I0。
特别的如果 KI,J0KI,J0那么表示这两样东西之间不会导致优惠。
注意 KI,JKI,J 可能大于 AA。
输出格式
一个整数为最小要花的钱数。
输入输出样例
输入 #1复制
1 1 0
输出 #1复制
1
输入 #2复制
3 3 0 2 4 2 0 2 4 2 0
输出 #2复制
7
说明/提示
样例解释 22。
先买第 22 样东西花费 33 元接下来因为优惠买 1,31,3 样都只要 22 元共 77 元。
同时满足多个“优惠”的时候聪明的明明当然不会选择用 44 元买剩下那件而选择用 22 元。
数据规模
对于 30%30% 的数据1≤B≤101≤B≤10。
对于 100%100% 的数据1≤B≤500,0≤A,KI,J≤10001≤B≤500,0≤A,KI,J≤1000。
2018.7.25新添数据一组
思路把价格看成边权位置看成点
源代码
#includeiostream
#includealgorithm
using namespace std;
const int B 505;
struct dists {int u, v, w;
}dist[B * B];
int a, b, k 0, u 0;
int NEXT[B * B];
int ans 0;
int find(int x) {if (x ! NEXT[x])return NEXT[x] find(NEXT[x]);return NEXT[x];
}
void Union(int x, int y) {int fx find(x);int fy find(y);if (fx ! fy)NEXT[fy] fx;
}
bool cmp(const dists x, const dists y) {return x.w y.w;
}
int main() {cin a b;for (int i 0; i B*B; i)NEXT[i] i;for (int i 1; i b; i) {for (int j 1; j b; j) {cin dist[k].w;dist[k].u i;dist[k].v j;if (dist[k].w 0)dist[k].w a;}}sort(dist 1, dist k 1, cmp);ans a;for (int i 1; i k; i) {if (find(dist[i].u) ! find(dist[i].v)) {Union(dist[i].u, dist[i].v);if (dist[i].w a)ans dist[i].w;elseans a;b--;if (b 0)break;}}cout ans;return 0;
}问题描述
有一个 SNS 被 NN 个用户使用他们的编号从 11 到 NN。
在这个 SNS 中两个用户可以成为朋友。
友谊是双向的如果用户 X 是用户 Y 的朋友那么用户 Y 也一定是用户 X 的朋友。
目前在 SNS 上有 MM 对朋友关系第 ii 对由用户 AiAi 和用户 BiBi 组成。
确定可以执行以下操作的最大次数
操作选择三个用户 X、Y 和 Z使得 X 和 Y 是朋友Y 和 Z 是朋友但 X 和 Z 不是朋友。让 X 和 Z 成为朋友。
约束条件 2≤N≤2×1052≤N≤2×105 0≤M≤2×1050≤M≤2×105 1≤AiBi≤N1≤AiBi≤N 这些对 是不同的。 (Ai,Bi)(Ai,Bi) 所有输入值都是整数。
输入
输入以以下格式从标准输入给出
NNMMA1A1B1B1⋮⋮AMAMBMBM输出
输出答案。
示例 1
InputcopyOutputcopy4 31 22 31 43
可以发生三次新的朋友关系方法如下 用户 和他们的朋友用户 的朋友用户 成为朋友 11 22 33 用户 和他们的朋友用户 的朋友用户 成为朋友 33 11 44 用户 和他们的朋友用户 的朋友用户 成为朋友 22 11 44
不会有四次或更多的新朋友关系。
示例 2
InputcopyOutputcopy3 00
如果没有初始的朋友关系就不会发生新的朋友关系。
示例 3
InputcopyOutputcopy10 81 22 33 44 56 77 88 99 1012
错误代码不知道错哪了求大佬教一教QWQ
#includeiostream
#includealgorithm
using namespace std;
const int M 2e5 5;
int NEXT[M];
int vis[M], bj[M];
int n, m, u, v;
int ans 0;
int val[1000];
int find(int x) {if (x ! NEXT[x])return NEXT[x] find(NEXT[x]);return NEXT[x];
}
void Union(int x, int y) {if (find(x) ! find(y))NEXT[find(y)] find(x);
}
int sy(int a[], int x,int n) {for (int i 0; i n; i) {if (a[i] x)return 1;}return 0;
}
int main() {cin n m;for (int i 0; i n; i)NEXT[i] i;for (int i 1; i m; i) {cin u v;Union(u, v);}for (int i 1; i n; i)vis[i] find(i);int k 1;for (int i 1; i n; i) {if (!sy(bj, vis[i], k)) {val[k - 1] i - 1;bj[k] vis[i];}}val[k-1] n;for (int i 0; i k - 1; i) {int c val[i 1] - val[i];ans c * (c - 1) / 2;}cout ans - m;return 0;
}
