题意:给一个 $$L (L \leq 10^6) $$ ,要求构造一张有向图,边从编号小的点连向编号大的点,从 $$1$$ 到 $$n$$ 恰好有 $$L-1$$ 条不同的路径,且路径长度是 $$[0,L-1]$$ 的数字且各不相同,最多20个点 60条边

$$2^{20}$$ 差不多是 $$10^6$$ 加上类似鬼谷子的钱袋的思想,所以做法大概是二进制分解

细节巨多,这代码是参照某聚聚的,改了一些实现以便我自己理解(我根本写不出来)…

大体做法是找到highbit然后把highbit以下的位数用 $$i$$ 连 $$i+1$$ 边权是 $$2^{i-1}$$ 的方法表示,剩余的从前面的点向终点连边(不这么做可能要用21个点)来表示

#include<bits/stdc++.h>
using namespace std;
struct edge {int u, v, w;};
vector<edge>G;
inline void add(int u, int v, int w) {
  G.push_back((edge) {u , v , w});
}
int main() {
  int L, t;
  cin >> L;
  for (int i = 0; i < 21; ++i) if (L & (1 << i)) t = i;
  for (int i = 1; i <= t - 1; i++) add(i, i+1, 1 << i-1), add(i, i+1, 0);
  add(t, 20, 0);
  add(t, 20, 1 << t-1);
  int g = 1 << t;
  while (g < L) {
    // cout << bitset<5>(L - g) << ' ';
    for(int i = 0; i < 21; ++i) if ((1 << i) & (L - g)) t = i; 
    add(t+1, 20, g);
    // cout << g << ' ' << bitset<5>(g) << endl;
    g |= 1 << t;
  }
  cout << "20 " << G.size() << endl;
  for (auto it = G.begin(); it != G.end(); ++it) cout << it->u << ' ' << it->v << ' ' << it->w << endl;
  return 0;
}
分类: 构造

发表评论

电子邮件地址不会被公开。 必填项已用*标注