graph

比较简单易懂的状压。 最初想懒一下把起点和终点也压进来然后发现刚好会超一点空间。然后不压进来的话就是100MB左右，很好奇MAIN上面64MB的内存应该怎么做。拿MAP么？ 代码各种难看啊郁闷。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t, v; edge *next; }; #define pow2(x) (1<<(x)) typedef pair <int, int> dspr; const int maxn = 20009; const int maxe = 400009; const int maxk = 20; const int maxz = pow2(20) + 3; int n, m, k, d[maxn]; int f[maxz][maxk], ds[maxk], dt[maxk], dk[maxk][maxk], ans; int g, pr[maxk]; edge *ep, *head[maxn]; dspr hp[maxe]; inline void addEdge(int u, int v, int w) {...

CDQ重构图。听上去比CDQ还高档的样子。 就是每层重新标号，把没有询问到的边拿来跑并查集。 最初是分开考虑然后可修复的并查集就T傻了。 #include <cstdio> #include <cstring> #include <cctype> #include <set> #include <algorithm> using namespace std; int _d_; #define readInt(_x_) { \ int& _s_ = _x_; \ while (!isdigit(_d_ = getchar())); \ _s_ = 0; \ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \ } const int maxn = 100009; const int maxm = 200009; const int maxl = 19; struct edge { int a, b, i; }; struct dset { int r[maxn], hp[maxn * 5], hv[maxn * 5], cnt;...

做过。但是不对。 迷之找负环。 初值直接赋为0，这样可以节省找没用的最短路的时间。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t; double v; edge *next; }; const int maxn = 3009; const int maxm = 10009; const double eps = 1e-9; const double finf = 1e20;  int n, m; bool iq[maxn]; double d[maxn], ave; edge *ep, *head[maxn], elst[maxm]; bool dfs(int p) { iq[p] = 1; for (edge* e = head[p]; e; e = e-> next) if (d[e-> t] - (d[p] + e-> v) > eps) {...