摸底考试 #1
T1 三值的排序
写一个程序计算出,给定的一个 $1,2,3$ 组成的数字序列,使用交换操作,排成升序所需的最少交换次数。
贪心:http://112.36.16.166:88/submission/48004
T2 日记
日记之中,写满了质数,两个质数之间如果没有其他质数,那么则称为相邻的质数。 给定 $N, k$ ,询问不超过 $N$ 的数中能够表示成连续的 $k$ 个质数之和的最大的数是多 少?
欧拉筛预处理素数然后直接暴力。
代码实现:http://112.36.16.166:88/submission/39019
T3 分蛋糕
分析
环形区间 DP,按照套路,把环复制一份。
设 $f_{l,r}$ 表示区间 $i$ 到 $j$,小 $Y$ 先手获得的最大贡献,转移就是小 $Y$ 的两种决策,然后确定小 $Z$ 的决策,转移即可,通过记忆化搜索实现较为容易,时间复杂度 $O(n^2)$。
T4 街灯
题目难度:普及+/提高
塔立于都市,攀登上塔,能够到达更远的地方。但是上塔,需要破解谜题。 有 $N$ 个数,但不给你,而是给了你 $\frac{N\times(N-1)}{2}$ 个数,代表它们两两的和。 那么,这 $N$ 个数是多少呢?
分析
先将读入的数字排序,显然最小值是 $a_1+a_2$,次小值 $a_1+a_3$。然后枚举 $a_2+a_3$ 的值,这样子就可以解出来 $a_1, a_2, a_3$。
在读入的数字中将 $a_1+a_2, a_2+a_3, a_1+a_3$ 删除,则剩下的数字最小的一定是 $a_1+a_4$ ,于是我们可以解出当前情况下的 $a_4$ 了。以此类推,就可以解出 $a_5, a_6 \dots$。
用一个 multiset 来快速实现加数和删数,注意到如果 $sum_i = sum_i - 1, i >3$,那么如果 $sum_{i-1}$ 能形成一组解,那么 $sum_i$ 也能形成一组与原来相同的解,可以特判或者用 unique 去重。
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
inline int read() {
int x = 0, f = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) f -= (ch == '-') * 2;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
return x * f;
}
const int N = 100010;
multiset<int> st;
int n, a[N], s[N];
vector<vector<int> > ans;
stack<int> stk;
void solve() {
while (stk.size()) st.insert(stk.top()), stk.pop();
for (int i = 1; i <= 3; i ++ ) {
for (int j = i + 1; j <= 3; j ++ ) {
st.erase(st.find(a[i] + a[j]));
stk.push(a[i] + a[j]);
}
}
for (int i = 4; i <= n; i ++ ) {
int x = (*st.begin()) - a[1];
if (x < a[i - 1]) return;
for (int j = 1; j <= i - 1; j ++ ) {
int sum = x + a[j];
if (st.find(sum) == st.end()) return;
st.erase(st.find(sum));
stk.push(sum);
}
a[i] = x;
}
vector<int> vt;
for (int i = 1; i <= n; i ++ ) vt.push_back(a[i]);
ans.push_back(vector<int>(n, 0));
}
signed main() {
n = read();
int tot = n * (n - 1) / 2;
for (int i = 1; i <= tot; i ++ ) s[i] = read(), st.insert(s[i]);
sort(s + 1, s + tot + 1);
for (int i = 3; i <= n; i ++ ) {
int t = s[1] + s[2] + s[i];
if (t & 1) continue;
int x = t / 2;
a[1] = x - s[i], a[2] = s[1] - a[1], a[3] = s[2] - a[1];
if (a[1] <= 0) continue;
solve();
}
ans.erase(unique(ans.begin(), ans.end()), ans.end());
printf("%d\n", ans.size());
for (int i = 0; i < ans.size(); i ++ ) {
for (int j = 0; j < ans[i].size(); j ++ ) {
printf("%d ", ans[i][j]);
}
puts("");
}
return 0;
}
NOIP 训练赛 #1
T3 智能小球
简要题意:给你一张带权完全图,初始时(时刻为 $0$)小 $k$ 会选择一个节点并放置一个点,之后每个时刻,这个点会随机移动到其他节点处,初始时小 $k$ 选择第 $i$ 个节点的概率为 $p_i$。
如果在 $t$ 时刻点在节点 $i$ 的位置,那么它移动到节点 $j$ 的概率为:
$$ \frac{dist(i, j)}{\sum_{k \ne i} dist(i, k)} $$
其中 $dist(i, j)$ 表示节点 $i$ 到节点 $j$ 最短路径的长度。
给出 $T$,求出在这个时刻点在每个节点的概率。
分析
考虑朴素 DP,设 $f_{t, i}$ 表示转移到时刻 $t$ 当前在 $i$ 点的概率,那么 $f_{t,i}=f_{t,i}+f_{t-1,j} \times dist(i, j) \ {\div \ sum_j}$。
使用 $floyd$ 可以快速求出两点之间的最短路径,我们提前预处理出 $sum_j$,转移的时间复杂度为 $O(1)$,但是仍然需要枚举 $t,i,j$,综上,这个 DP 的时间复杂度为 $O(tn^2+n^3)$。
这个 DP 式子一看就很像矩阵快速幂能优化的东西,结合 $T \le 1e9$,基本可以确定是矩阵快速幂优化 DP。
设矩阵 $F$ 表示一个 $1 \times n$ 的矩阵,矩阵 $Mat$ 表示 $n \times n$ 的转移矩阵,那么原来的 $dist(i, j) \ {\div \ sum_j}$ 就是转移矩阵上的系数。
用矩阵快速幂的时候,是从一个状态推到另一个状态,所以将 $sum_j$ 改为 $sum_i$。
代码实现
#include <bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, f = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) f -= (ch == '-') << 1;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
return x * f;
}
const int N = 202;
int n, hyl;
int g[N][N], sum[N];
double p[N];
struct Matrix {
double a[N][N];
Matrix() {
for (int i = 0; i <= n; i ++ ) {
for (int j = 0; j <= n; j ++ ) {
a[i][j] = 0;
}
}
}
Matrix operator * (const Matrix &b) const {
Matrix res;
for (int i = 1; i <= n; i ++ ) {
for (int k = 1; k <= n; k ++ ) {
for (int j = 1; j <= n; j ++ ) {
res.a[i][j] += a[i][k] * b.a[k][j];
}
}
}
return res;
}
} mat, f;
Matrix qpow(Matrix a, int b) {
Matrix res = a; b -- ;
for (; b; b >>= 1) {
if (b & 1) res = res * a;
a = a * a;
}
return res;
}
signed main() {
n = read(), hyl = read();
for (int i = 1; i <= n; i ++ ) scanf("%lf", &p[i]);
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= n; j ++ ) {
g[i][j] = read();
}
}
for (int k = 1; k <= n; k ++ ) {
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= n; j ++ ) {
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
}
}
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= n; j ++ ) {
sum[i] += g[i][j];
}
}
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= n; j ++ ) {
mat.a[i][j] = (double)g[i][j] / sum[i];
}
}
for (int i = 1; i <= n; i ++ ) f.a[1][i] = p[i];
Matrix ans = f * qpow(mat, hyl);
for (int i = 1; i <= n; i ++ ) printf("%.6lf\n", ans.a[1][i]);
return 0;
}
NOIP 训练赛 #2
T4 顽皮的猴子
分析
对于 $50\%$ 的数据,就是求路径上的最小值,直接倍增即可。
对于 $100\%$ 的数据,用队列维护路径上的前 $k$ 小值,仿照上面的做法即可。
代码实现
50 pts:http://112.36.16.166:88/submission/42557
#include <bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, f = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) f -= (ch == '-') << 1;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
return x * f;
}
const int N = 100010, M = 2 * N;
int n, m, q;
int h[N], e[M], ne[M], idx;
int dep[N], f[N][25];
bool vis[N];
class Queue {
public:
int q[15], ql = 1, qr = 0;
void push(int x) { q[ ++ qr] = x; }
int size() { return qr - ql + 1; }
int front() { return q[ql]; }
int back() { return q[qr]; }
int pop() { ql ++ ; }
int clear() { ql = 1, qr = 0; }
} g[N][25], c[N];
void add(int a, int b) {
e[ ++ idx] = b, ne[idx] = h[a], h[a] = idx;
}
Queue merge(Queue a, Queue b, int k) {
Queue res;
while ((a.size() || b.size()) && res.size() < k) {
if (a.size() && b.size()) {
if (a.front() < b.front()) res.push(a.front()), a.pop();
else res.push(b.front()), b.pop();
}
else if (!a.size()) res.push(b.front()), b.pop();
else if (!b.size()) res.push(a.front()), a.pop();
}
return res;
}
void bfs(int st) {
queue<int> q;
q.push(st);
dep[st] = 1;
vis[st] = true;
while (q.size()) {
auto t = q.front(); q.pop();
for (int i = h[t]; i; i = ne[i]) {
int j = e[i];
if (vis[j]) continue;
vis[j] = true;
dep[j] = dep[t] + 1;
f[j][0] = t;
g[j][0] = c[t];
for (int k = 1; k <= 21; k ++ ) {
int fa = f[j][k - 1];
f[j][k] = f[fa][k - 1];
g[j][k] = merge(g[j][k - 1], g[fa][k - 1], 10);
}
q.push(j);
}
}
}
Queue getmin(int a, int b, int k) {
if (dep[a] < dep[b]) swap(a, b);
int d = dep[a] - dep[b];
Queue res = c[a];
for (int i = 0; i <= 21; i ++ ) {
if (d >> i & 1) {
res = merge(res, g[a][i], k);
a = f[a][i];
}
}
if (a == b) return res;
res = merge(res, c[b], k);
for (int i = 21; i >= 0; i -- ) {
if (f[a][i] == f[b][i]) continue;
res = merge(res, g[a][i], k);
res = merge(res, g[b][i], k);
a = f[a][i], b = f[b][i];
}
res = merge(res, g[a][0], k);
return res;
}
signed main() {
n = read(), m = read(), q = read();
for (int i = 1; i < n; i ++ ) {
int a = read(), b = read();
add(a, b), add(b, a);
}
for (int i = 1; i <= m; i ++ ) {
int live_ = read();
c[live_].push(i);
}
bfs(1);
while (q -- ) {
int a = read(), b = read(), k = read();
Queue ans = getmin(a, b, k);
if (ans.size() == 0) puts("0");
else {
printf("%d ", min(k, ans.size()));
for (int i = ans.ql; i <= ans.qr; i ++ ) printf("%d ", ans.q[i]);
puts("");
}
}
return 0;
}
NOIP 训练赛 #6
T4 简单题(PYYZ-2330)
题目难度:提高+/省选-
简要题意,给你一张 $n$ 个点 $m$ 条边的无向图,计算如果一条边能成为最小生成树上的边可以达到的最大边权。
对于 $75 \%$ 的数据, $N, M \leq 8000$。
对于 $100\%$ 的数据, $1 \leq N \leq 10^5, N-1 \leq M \leq 10^6, 0 \leq w_i \leq 10^9$。
分析
定义一条路径的代价 $cost_{u,v}$ 为 $u$ 点到达 $v$ 点路径上最大边权的最小值。
对于每条边的最大费用,答案为删除这条边后,这条边的两个端点的代价。
所以对于 $75\%$ 的数据,可以直接跑 $Dijkstra$,即把原先判断是否满足三角不等式的 $dist_v > dist_u + w$ 更改为 $dist_v > max\{dist_u, w\}$,这也是满足 $Dijkstra$ 的贪心性质的。
当然也可以跑 $Kruskal$ 重构树来得到这 $75pts$(最小瓶颈路)。
对于 $100\%$ 的数据,使用最小生成树,显然对于一条边有两种情况:
对于非树边,一条非树边如果要成为树边,那么边权最大是树上两点之间路径上的最大边权。
- 直接树上倍增即可。
对于树边,删除这条边后,最小生成树会变成两个连通块,如果这条边依然是树边,那么它的边权必须要 $\leq$ 连接两个联通块边集中边权的最小值(不然可以通过另一条路径连接两个联通块且代价更小)。
- 用非树边去更新每条树边的权值,这显然可以用树剖来做,下面是倍增的做法(zpl 太强啦)。
- 设 $h_{i,j}$ 表示 $i$ 点到其 $2^{j}$ 级祖先的答案。
- 考虑一种类似 $lazytag$ 的做法,每次倍增跳祖先,并在跳的过程中更新 $h_{i, j}$,做完后 $pushdown$ 下传标记。
void modify(int a, int b, int c) {
if (dep[a] < dep[b]) swap(a, b);
int d = dep[a] - dep[b], res = 0;
for (int i = 18; i >= 0; i -- ) (d >> i & 1) ? lazy[a][i] = min(lazy[a][i], c), a = f[a][i] : 0;
if (a == b) return;
for (int i = 18; i >= 0; i -- ) {
if (f[a][i] == f[b][i]) continue;
lazy[a][i] = min(lazy[a][i], c);
lazy[b][i] = min(lazy[b][i], c);
a = f[a][i], b = f[b][i];
}
lazy[a][0] = min(lazy[a][0], c);
lazy[b][0] = min(lazy[b][0], c);
}
void pushdown() {
for (int k = 18; k; k -- ) {
for (int i = 1; i <= n; i ++ ) {
lazy[i][k - 1] = min(lazy[i][k - 1], lazy[i][k]);
lazy[f[i][k - 1]][k - 1] = min(lazy[f[i][k - 1]][k - 1], lazy[i][k]);
}
}
}
代码实现
Dijkstra(75 pts)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
inline string readstr() {
string s = ""; char ch = getchar();
for (; isspace(ch); ch = getchar());
for (; !isspace(ch); ch = getchar()) s.push_back(ch);
return s;
}
inline int read() {
int x = 0, f = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) f -= (ch == '-') << 1;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
return x * f;
}
const int N = 100010, M = 20 * N;
int n, m, dist[N];
int h[N], w[M], e[M], ne[M], idx = 1;
bool del[M], vis[N];
void add(int a, int b, int c) {
e[ ++ idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx;
}
void dijkstra(int st) {
fill(dist, dist + n + 1, 1000000000);
memset(vis, 0, sizeof vis);
priority_queue<PII, vector<PII>, greater<PII>> q;
q.emplace(0, st);
dist[st] = 0;
while (q.size()) {
auto t = q.top(); q.pop();
int u = t.second;
if (vis[u]) continue;
vis[u] = true;
for (int i = h[u]; i; i = ne[i]) {
if (del[i]) continue;
int j = e[i];
if (dist[j] > max(dist[u], w[i])) {
dist[j] = max(dist[u], w[i]);
q.emplace(dist[j], j);
}
}
}
}
int main() {
n = read(), m = read();
for (int i = 1; i <= m; i ++ ) {
int a = read(), b = read(), c = read();
add(a, b, c), add(b, a, c);
}
for (int i = 2; i <= idx; i += 2) {
del[i] = del[i ^ 1] = true;
dijkstra(e[i]);
printf("%d\n", dist[e[i ^ 1]]);
del[i] = del[i ^ 1] = false;
}
return 0;
}
最小生成树+倍增(100 pts)
#include <bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, f = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) f -= (ch == '-') * 2;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
return x * f;
}
const int N = 100010, M = 10 * N;
int n, m;
int h[N], w[N << 1], e[N << 1], ne[N << 1], idx = 1;
int f[N][20], g[N][20], lazy[N][20];
int fa_edge[N], dep[N], in_tree[M], ans[M], edge_id[N << 1];
struct Edge {
int a, b, c, id;
Edge() {};
Edge(int _a, int _b, int _c, int _id): a(_a), b(_b), c(_c), id(_id) {};
bool operator < (const Edge& x) { return c < x.c; }
} edges[M];
void add(int a, int b, int c) {
e[ ++ idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx;
}
class DSU {
public:
int p[N], sz[N];
DSU() { for (int i = 1; i < N; p[i] = i, sz[i] = 1, i ++ ); }
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void merge(int a, int b) {
int pa = find(a), pb = find(b);
if (sz[pa] < sz[pb]) sz[pb] += sz[pa], p[pa] = pb;
else sz[pa] += sz[pb], p[pb] = pa;
}
bool check(int a, int b) { return find(a) == find(b); }
} dsu;
void bfs(int st) {
queue<int> q;
q.push(st);
dep[st] = 1;
while (q.size()) {
auto t = q.front(); q.pop();
for (int i = h[t]; i; i = ne[i]) {
int j = e[i];
if (dep[j]) continue;
dep[j] = dep[t] + 1;
f[j][0] = t, g[j][0] = w[i];
fa_edge[j] = edge_id[i];
for (int k = 1; k <= 18; k ++ ) {
int fa = f[j][k - 1];
f[j][k] = f[fa][k - 1];
g[j][k] = max(g[j][k - 1], g[fa][k - 1]);
}
q.push(j);
}
}
}
int get_max(int a, int b) {
if (dep[a] < dep[b]) swap(a, b);
int d = dep[a] - dep[b], res = 0;
for (int i = 18; i >= 0; i -- ) (d >> i & 1) ? res = max(res, g[a][i]), a = f[a][i] : 0;
if (a == b) return res;
for (int i = 18; i >= 0; i -- ) {
if (f[a][i] == f[b][i]) continue;
res = max({res, g[a][i], g[b][i]});
a = f[a][i], b = f[b][i];
}
return max({res, g[a][0], g[b][0]});
}
int lca(int a, int b) {
if (dep[a] < dep[b]) swap(a, b);
int d = dep[a] - dep[b];
for (int i = 18; i >= 0; i -- ) (d >> i & 1) ? a = f[a][i] : 0;
if (a == b) return a;
for (int i = 18; i >= 0; i -- ) {
if (f[a][i] == f[b][i]) continue;
a = f[a][i], b = f[b][i];
}
return f[a][0];
}
void kruskal() {
sort(edges + 1, edges + m + 1);
for (int i = 1; i <= m; i ++ ) {
int a = edges[i].a, b = edges[i].b, c = edges[i].c;
if (!dsu.check(a, b)) {
in_tree[i] = true;
add(a, b, c), add(b, a, c);
edge_id[idx ^ 1] = edge_id[idx] = edges[i].id;
dsu.merge(a, b);
}
}
}
void modify(int a, int b, int c) {
if (dep[a] < dep[b]) swap(a, b);
int d = dep[a] - dep[b], res = 0;
for (int i = 18; i >= 0; i -- ) (d >> i & 1) ? lazy[a][i] = min(lazy[a][i], c), a = f[a][i] : 0;
if (a == b) return;
for (int i = 18; i >= 0; i -- ) {
if (f[a][i] == f[b][i]) continue;
lazy[a][i] = min(lazy[a][i], c);
lazy[b][i] = min(lazy[b][i], c);
a = f[a][i], b = f[b][i];
}
lazy[a][0] = min(lazy[a][0], c);
lazy[b][0] = min(lazy[b][0], c);
}
void pushdown() {
for (int k = 18; k; k -- ) {
for (int i = 1; i <= n; i ++ ) {
lazy[i][k - 1] = min(lazy[i][k - 1], lazy[i][k]);
lazy[f[i][k - 1]][k - 1] = min(lazy[f[i][k - 1]][k - 1], lazy[i][k]);
}
}
}
int main() {
n = read(), m = read();
for (int i = 1; i <= m; i ++ ) {
int a = read(), b = read(), c = read();
edges[i] = Edge(a, b, c, i);
}
kruskal();
bfs(1);
for (int i = 1; i <= n; i ++ ) fill(lazy[i], lazy[i] + 18 + 1, 1000000000);
for (int i = 1; i <= m; i ++ ) {
if (!in_tree[i]) {
int a = edges[i].a, b = edges[i].b, c = edges[i].c;
ans[edges[i].id] = get_max(a, b);
modify(a, b, c);
}
}
pushdown();
for (int i = 2; i <= n; i ++ ) ans[fa_edge[i]] = lazy[i][0];
for (int i = 1; i <= m; i ++ ) printf("%d\n", ans[i]);
return 0;
}
同学的树剖(100 pts)
#include <bits/stdc++.h>
using namespace std;
inline int read() {
int s = 0, k = 1;
char c = getchar();
while (c > '9' || c < '0') {
if (c == '-') k = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
s = (s << 3) + (s << 1) + (c ^ 48);
c = getchar();
}
return s * k;
}
const int N = 1e5 + 10, M = 1e6 + 10;
int n, fat[N], tim, id[N], a[N], dfn[N], m, head[N], nq, cnt, dis[N][19], fa[N][19], dep[N], top[N], son[N],
siz[N], ans[M];
bool vks[M];
queue<int>q;
struct edge {
int u, v, w, id;
} qu[M];
struct EDGE {
int v, nxt, w;
} e[N << 1];
struct node {
int tag, v;
} t[N << 2];
void add(int u, int v, int w) {
e[++cnt].v = v;
e[cnt].w = w;
e[cnt].nxt = head[u];
head[u] = cnt;
}
bool cmp(edge a, edge b) {
return a.w < b.w;
}
int find(int x) {
if (fat[x] == x) return x;
else return fat[x] = find(fat[x]);
}
void kruskal() {
sort(qu + 1, qu + 1 + m, cmp);
for (int i = 1; i <= n; i++) fat[i] = i;
for (int i = 1, x, y; i <= m; i++) {
x = qu[i].u, y = qu[i].v;
x = find(x), y = find(y);
if (x != y) {
fat[x] = y;
vks[i] = true;
add(qu[i].u, qu[i].v, qu[i].w);
add(qu[i].v, qu[i].u, qu[i].w);
}
}
}
void bfs(int s) {
dep[s] = 1;
q.push(s);
while (!q.empty()) {
int x = q.front(); q.pop();
for (int i = head[x]; i; i = e[i].nxt) {
int v = e[i].v;
if (dep[v]) continue;
dep[v] = dep[x] + 1;
fa[v][0] = x;
dis[v][0] = e[i].w;
q.push(v);
for (int j = 1; j <= nq; j++)
fa[v][j] = fa[fa[v][j - 1]][j - 1],
dis[v][j] = max(dis[v][j - 1], dis[fa[v][j - 1]][j - 1]);
}
}
}
void dfs1(int x, int fa) {
siz[x] = 1;
for (int i = head[x]; i; i = e[i].nxt) {
int v = e[i].v;
if (v == fa) continue;
dfs1(v, x);
siz[x] += siz[v];
if (siz[v] > siz[son[x]]) son[x] = v;
}
}
void dfs2(int x, int t) {
top[x] = t;
dfn[x] = ++tim;
id[tim] = x;
if (son[x]) dfs2(son[x], t);
for (int i = head[x]; i; i = e[i].nxt) {
int v = e[i].v;
if (v != fa[x][0] && v != son[x]) dfs2(v, v);
}
}
void build(int s, int l, int r) {
t[s].v = 1e9;
t[s].tag = 1e9;
if (l == r) return;
int mid = (l + r) >> 1;
build(s << 1, l, mid);
build(s << 1 | 1, mid + 1, r);
}
int qdis(int x, int y) {
int t = 0;
if (dep[x] > dep[y]) swap(x, y);
for (int i = nq; i >= 0; i--)
if (dep[fa[y][i]] >= dep[x])
t = max(t, dis[y][i]), y = fa[y][i];
if (x == y) return t;
for (int i = nq; i >= 0; i--)
if (fa[x][i] != fa[y][i])
t = max({t, dis[x][i], dis[y][i]}), x = fa[x][i], y = fa[y][i];
return max({t, dis[x][0], dis[y][0]});
}
void pushdown(int s) {
t[s << 1].v = min(t[s << 1].v, t[s].tag);
t[s << 1 | 1].v = min(t[s << 1 | 1].v, t[s].tag);
t[s << 1].tag = min(t[s << 1].tag, t[s].tag);
t[s << 1 | 1].tag = min(t[s << 1 | 1].tag, t[s].tag);
t[s].tag = 1e9;
}
void update(int s, int l, int r, int L, int R, int v) {
if (L > R) return;
if (L <= l && r <= R) {
t[s].v = min(t[s].v, v);
t[s].tag = min(t[s].tag, v);
return;
}
pushdown(s);
int mid = (l + r) >> 1;
if (L <= mid) update(s << 1, l, mid, L, R, v);
if (R > mid) update(s << 1 | 1, mid + 1, r, L, R, v);
}
void getans(int s, int l, int r) {
if (l == r) {
a[id[l]] = t[s].v;
return;
}
pushdown(s);
int mid = (l + r) >> 1;
getans(s << 1, l, mid);
getans(s << 1 | 1, mid + 1, r);
}
void upd(int x, int y, int w) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
update(1, 1, tim, dfn[top[x]], dfn[x], w);
x = fa[top[x]][0];
}
if (dep[x] > dep[y]) swap(x, y);
update(1, 1, tim, dfn[x] + 1, dfn[y], w);
}
int main() {
n = read();
m = read();
nq = log2(n);
for (int i = 1, u, v, w; i <= m; i++) {
u = read(), v = read();
w = read();
qu[i] = {u, v, w, i};
}
kruskal();
bfs(1);
dfs1(1, 0);
dfs2(1, 1);
build(1, 1, tim);
for (int i = 1; i <= m; i++) {
if (!vks[i]) {
upd(qu[i].u, qu[i].v, qu[i].w);
ans[qu[i].id] = qdis(qu[i].u, qu[i].v);
}
}
getans(1, 1, tim);
for (int i = 1; i <= m; i++) {
if (vks[i]) {
if (dfn[qu[i].u] > dfn[qu[i].v]) swap(qu[i].u, qu[i].v);
ans[qu[i].id] = a[qu[i].v];
}
}
for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
return 0;
}