最短路
- \(Floyd\) 算法
- \(Dijkstra\) 算法
- \(SPFA\) 算法
这些算法都很熟悉,基本的就不多说了。
T1 1993 小K的农场
差分约束,跑一遍 \(spfa\) 判断有没有负环就可以了。
struct node{
int v,w;
};
int n,m;
vector<node> e[N];
int dis[N];
bool flag[N];
int cnt[N];
bool spfa() {
queue<int> q;
memset(dis,0x3f,sizeof dis);
q.push(0);
dis[0] = 0;
while (q.size()) {
auto u = q.front();
q.pop();
flag[u] = false;
for (auto it : e[u]) {
int v = it.v,w = it.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (!flag[v]) {
cnt[v] ++;
if (cnt[v] > n) return false;
flag[v] = true;
q.push(v);
}
}
}
}
return true;
}
int main(){
n = fr(),m = fr();
for (int i = 1; i <= n; i ++) {
e[0].push_back({i,0});
}
int type,a,b,w;
while (m --) {
type = fr();
if (type == 1) {
a = fr(),b = fr(),w = fr();
e[a].push_back({b,-w});
} else if (type == 2) {
a = fr(),b = fr(),w = fr();
e[b].push_back({a,w});
} else {
a = fr(),b = fr();
e[a].push_back({b,0});
e[b].push_back({a,0});
}
}
if (spfa()) yj;
else wj;
return 0;
}
2757 等差子序列
是昨天的题,哈希。
因为他说了这是一个连续的排列,所以我们一个个遍历,如果遍历到了就将当前位置标记为 \(1\) ,只有当这个标记数组一直是回文串的时候,他才没有等差数列。
举个例子,如果序列是 \(3,2,1\) ,那么这个标记数组的变化就是 \(001 -> 011 -> 111\) ,可以发现第一个和第二个不是回文串,所以这里是有等差数列的。
然后判断回文串的话就用线段树结合哈希来判断是不是回文串,维护的话就维护正着和倒着两个哈希值。
struct node{
lwl pre,suf;
}tr[N << 2];
int n;
int w[N];
lwl poww[N];
void init(){
poww[0] = 1;
for (int i = 1; i < N; i ++) {
poww[i] = poww[i - 1] * p % mod;
}
}
void pushup(int idx,int lenl,int lenr) {
tr[idx].pre = tr[ir].pre + tr[il].pre * poww[lenr];
tr[idx].pre %= mod;
tr[idx].suf = tr[ir].suf * poww[lenl] + tr[il].suf;
tr[idx].suf %= mod;
}
void modify(int L,int R,int l,int r,int idx) {
if (L == l && R == r) {
tr[idx].pre = 1;
tr[idx].suf = 1;
return ;
}
int mid = (L + R) >> 1;
if (mid >= l) modify(L,mid,l,r,il);
if (mid < r) modify(mid + 1,R,l,r,ir);
pushup(idx,mid - L + 1,R - mid);
}
lwl query(int L,int R,int l,int r,int idx,int type) {
if (L > R || l > r) return 0;
if (L >= l && R <= r) {
if (type == 1) return tr[idx].pre;
else return tr[idx].suf;
}
int mid = (L + R) >> 1;
if (r <= mid) return query(L,mid,l,r,il,type);
if (l > mid) return query(mid + 1,R,l,r,ir,type);
lwl ll = query(L,mid,l,r,il,type);
lwl rr = query(mid + 1,R,l,r,ir,type);
lwl ans;
if (type == 1) ans = ll * poww[min(r,R) - mid] + rr;
else ans = rr * poww[mid - (max(L,l)) + 1] + ll;
return ans % mod;
}
int main(){
int T = fr();
init();
while (T --) {
n = fr();
for (int i = 1; i <= n; i ++) {
w[i] = fr();
}
bool flag = false;
memset(tr,0,sizeof tr);
for (int i = 1; i <= n; i ++) {
int len = min(w[i] - 1,n - w[i]);
lwl a = query(1,n,w[i] - len,w[i] - 1,1,1);
lwl b = query(1,n,w[i] + 1,w[i] + len,1,2);
if (a != b) {
flag = true;
break;
}
modify(1,n,w[i],w[i],1);
}
if (flag) yj;
else wj;
}
return 0;
}
还有就是,我宣布哈希是玄学算法!!!!
T3 5304 旅行者
这个题是最短路加上二进制,搞两个源点,一个作为起点一个作为终点。然后对于每一个特殊的点,把二进制的每一位都遍历一遍,如果 \(j \&(1 << i)\) 的话,就先把他和起点连一条长度为 \(0\) 的边,然后其余点和终点连一条长度为 \(0\) 的边,然后从起点到终点跑一遍 \(dij\) 最短路,然后再反过来跑一遍,在其中取最小值就是答案。
因为两个点之间的最短距离那么这两个点的编号一定是不一样的,这样就可以把所有两个点之间的距离最小值给求出来,但是不知道是哪两个点。(好像再开一个数组是可以的(?))
然后就是这一题不要忘记开 \(lwl\) 了。
struct node{
int v;
lwl w;
};
int n,m,k;
int S,T;
vector<node> e[N],temp[N];
int w[N];
lwl dis[N];
bool flag[N];
lwl dij() {
memset(dis,0x3f,sizeof dis);
memset(flag,0,sizeof flag);
priority_queue<pii,vector<pii>,greater<pii> > q;
dis[S] = 0;
q.push({dis[S],S});
while (q.size()) {
auto t = q.top();
q.pop();
int u = t.se;
if (flag[u]) continue;
for (auto it : e[u]) {
int v = it.v;
lwl val = it.w;
if (dis[v] > dis[u] + val) {
dis[v] = dis[u] + val;
q.push({dis[v],v});
}
}
flag[u] = true;
}
return dis[T];
}
int main(){
int TT = fr();
while (TT --) {
n = fr(),m = fr(),k = fr();
for (int i = 1; i <= n + 2; i ++) {
temp[i].clear();
}
int a,b,ww;
while (m --) {
a = fr(),b = fr(), ww = fr();
temp[a].push_back({b,ww});
}
for (int i = 1; i <= k; i ++) w[i] = fr();
S = n + 1,T = n + 2;
lwl ans = linf;
for (int i = 0; (1 << i) <= k; i ++) {
for (int j = 1; j <= n + 2; j ++) {
e[j] = temp[j];
}
for (int j = 1; j <= k; j ++) {
if (j & (1 << i)) {
e[S].push_back({w[j],0});
} else {
e[w[j]].push_back({T,0});
}
}
ans = min(ans,dij());
for (int j = 1; j <= n + 2; j ++) {
e[j] = temp[j];
}
for (int j = 1; j <= k; j ++) {
if (j & (1 << i)) {
e[w[j]].push_back({T,0});
} else {
e[S].push_back({w[j],0});
}
}
ans = min(ans,dij());
}
fw(ans);
ch;
}
return 0;
}
练习
今天是 \(OI\) 赛制,但是其中三题洛谷上面都有原题,所以我的评价是 \(OI\) 但不完全 \(OI\) 。前面三题比较简单,就是第一题一开始无解的时候要输出 “No important cities.”,然后我一开始写的时候没有看到还有一个英文句号,还是 \(Tak1na\) 说了之后才发现的
第四题一开始正解写挂了,然后比赛结束之后找了 \(Richard\_H\) 的 \(dij\) 写法,过了。然后去找老师问正解怎么改,改了几个地方之后才 \(AC\)
A.重要的城市
用 \(Floyd\) 算最短路的过程中把每两个点之间的最短路的数量都算出来,如果 \(cnt[i][j] = cnt[i][k] \times cnt[k][j]\) 就说明 \(i,j\) 之间的最短路一定要经过 \(k\) 点,然后这样处理之后就可以求了。
int n,m;
lwl cnt[N][N];
int dis[N][N];
int main(){
memset(dis,0x3f,sizeof dis);
n = fr(),m = fr();
for (int i = 1; i <= n; i ++)
dis[i][i] = 0;
for (int i = 1; i <= m; i ++) {
int a = fr(),b = fr(),c = fr();
dis[a][b] = dis[b][a] = c;
cnt[a][b] = cnt[b][a] = 1;
}
for (int k = 1; k <= n; k ++) {
for (int i = 1; i <= n; i ++) {
if (i == k) continue;
for (int j = 1; j <= n; j ++) {
if (j == k || j == i) continue;
if (dis[i][j] > dis[i][k] + dis[k][j]) {
dis[i][j] = dis[i][k] + dis[k][j];
cnt[i][j] = cnt[i][k] * cnt[k][j];
} else if (dis[i][j] == dis[i][k] + dis[k][j]) {
cnt[i][j] += cnt[i][k] * cnt[k][j];
}
}
}
}
bool st = false;
for (int k = 1; k <= n; k ++) {
bool flag = false;
for (int i = 1; i <= n; i ++) {
if (i == k) continue;
for (int j = 1; j <= n; j ++) {
if (j == k || j == i) continue;
if (cnt[i][j] == cnt[i][k] * cnt[k][j] && dis[i][j] == dis[i][k] + dis[k][j]) {
fw(k),kg;
st = true,flag = true;
break;
}
}
if (flag) break;
}
}
if (!st) wj;
return 0;
}
B.新年好
这个是 \(ACwing\) 上面以前做过的原题,就是先把这六个点的单源最短路都求出来,然后用 \(nextpermutation\) 或者 \(dfs\) 枚举一下每一个走过的顺序就可以了。感觉挺暴力的。
然后这一题根据 \(Tak1na\) 所说,如果用 \(spfa\) 会 \(T\) 掉,然后用 \(SLF\) 优化在洛谷也有一个点过不了。但是信友队这里 \(spfa\) 可以冒过去,数据就是水啦。
struct node{
int v,w;
};
int n,m;
int a[7];
vector<node> e[N];
int dis[7][N];
int siz[N];
bool flag[N];
void dij(int st,int dis[]) {
memset(dis,0x3f,sizeof siz);
memset(flag,0,sizeof flag);
priority_queue<pii,vector<pii>,greater<pii> > q;
dis[st] = 0;
q.push({dis[st],st});
while (q.size()) {
auto t = q.top();
q.pop();
int u = t.se;
if (flag[u]) continue;
for (auto it : e[u]) {
int v = it.v,w = it.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (!flag[v])
q.push({dis[v],v});
}
}
flag[u] = true;
}
}
int main(){
n = fr(),m = fr();
for (int i = 2; i <= 6; i ++) {
a[i] = fr();
}
a[1] = 1;
for (int i = 1; i <= m; i ++) {
int a = fr(),b = fr(),w = fr();
e[a].push_back({b,w});
e[b].push_back({a,w});
}
for (int i = 1; i <= 6; i ++) {
dij(a[i],dis[i]);
}
int h[7] = {0,1,2,3,4,5,6};
int ans = inf;
do{
int res = dis[1][a[h[2]]];
for (int i = 2; i <= 5; i ++) {
res += dis[h[i]][a[h[i + 1]]];
}
ans = min(ans,res);
} while (next_permutation(h + 2,h + 7));
fw(ans);
ch;
return 0;
}
C.飞行路线
分层图,把每一个航班都弄成好几个点,然后连边的时候就每次都连多一点,然后最后算的时候就取一个 \(min\) 就可以了。理论上来说如果直接用 \(dis[T + n * k]\) 也是可以的,但是我没有试,反正次数也不多,跑一跑算了。
这个要注意的一点就是如果 \(k = 10\) 的话其实是有 \(11 * n\) 个点的,所以开数组的时候不能只开十倍,不然会 \(RE\) 一个点(在洛谷上交的时候 \(RE\) 了)
struct node {
int v,w;
};
int n,m,k;
int S,T;
vector<node> e[N];
lwl dis[N];
bool flag[N];
void dij() {
memset(dis,0x3f,sizeof dis);
memset(flag,0,sizeof flag);
priority_queue<pii,vector<pii>,greater<pii> > q;
dis[S] = 0;
q.push({dis[S],S});
while (q.size()) {
auto t = q.top();
q.pop();
int u = t.se;
if (flag[u]) continue;
for (auto it : e[u]) {
int v = it.v,w = it.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (!flag[v]) q.push({dis[v],v});
}
}
flag[u] = true;
}
}
int main(){
n = fr(), m = fr(), k = fr();
S = fr(), T = fr();
while (m --) {
int a = fr(), b = fr(), w = fr();
e[a].push_back({b,w});
e[b].push_back({a,w});
for (int i = 1; i <= k; i ++) {
a += n,b += n;
e[a].push_back({b,w});
e[b].push_back({a,w});
e[a - n].push_back({b,0});
e[b - n].push_back({a,0});
}
}
dij();
lwl ans = linf;
for (int i = 0; i <= k; i ++) {
ans = min(ans,dis[T + i * n]);
}
fw(ans);
return 0;
}
D.护送
这个题一开始正解写挂了,气死了。
就是用了 \(Floyd\) 的性质:用于松弛的点只有之前遍历过的 \(k\) 点。所以我们就把所有点按照 \(c_i\) 排一个序,保证每一条当前的最短路的 \(c_i\) 最大值要么是在起点和终点处,要么就是在 \(k\) 点。
然后要注意的就是内层的两个循环都要从 \(1 - n\) 全部跑一遍,要不然有些情况没有考虑到。还有就是这里的 \(temp[i][i]\) 和 \(dis[i][i]\) 要初始化为 \(0\) ,要不然就会痛失就十分。
int n,m;
int dis[N][N];
int temp[N][N];
int w[N];
int id[N];
bool cmp(int a,int b) {
return w[a] < w[b];
}
int main(){
memset(temp,0x3f,sizeof temp);
memset(dis,0x3f,sizeof dis);
n = fr(),m = fr();
for (int i = 1; i <= n; i ++) {
w[i] = fr();
}
for (int i = 1; i <= m; i ++) {
int a = fr(),b = fr(),c = fr();
temp[a][b] = temp[b][a] = min(temp[a][b],c);
}
for (int i = 1; i <= n; i ++) {
id[i] = i;
}
for (int i = 1; i <= n; i ++) {
dis[i][i] = 0;
temp[i][i] = 0;
}
sort(id + 1,id + 1 + n,cmp);
for (int k = 1; k <= n; k ++) {
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
if (j == i) continue;
if (temp[id[i]][id[j]] > temp[id[i]][id[k]] + temp[id[k]][id[j]])
temp[id[i]][id[j]] = temp[id[i]][id[k]] + temp[id[k]][id[j]];
}
}
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
dis[id[i]][id[j]] = min(dis[id[i]][id[j]],temp[id[i]][id[k]] + temp[id[k]][id[j]] + w[id[max(i,max(j,k))]]);
}
}
}
int Q = fr();
while (Q --) {
int a = fr(),b = fr();
fw(dis[a][b]);
ch;
}
return 0;
}
E.种树
差分约束,然后每一个 \(dis\) 都维护到那里的前缀和就可以。然后可以把题目给的几个等式都转化为不等式,然后差分约束跑一遍最长路直接输出 \(dis[n]\) 就可以了。
然后这里的 \(dis\) 要记得初始化为 \(-inf\) ,不然就会寄掉 \(20\) 分(不是我寄的,但是 \(Richard\_H\)寄了)
struct node{
int v,w;
};
int n,m;
int w[N];
int dis[N];
bool flag[N];
vector<node> e[N];
void spfa() {
memset(dis,-0x3f,sizeof dis);
memset(flag,0,sizeof flag);
queue<int> q;
q.push(0);
dis[0] = 0;
while (q.size()) {
auto u = q.front();
q.pop();
flag[u] = false;
for (auto it : e[u]) {
int v = it.v,w = it.w;
if (dis[v] < dis[u] + w) {
dis[v] = dis[u] + w;
if (!flag[v]) {
q.push(v);
flag[v] = true;
}
}
}
}
}
int main(){
n = fr(),m = fr();
for (int i = 1; i <= n; i ++) {
w[i] = fr();
e[i].push_back({i - 1,-w[i]});
e[i - 1].push_back({i,0});
}
while (m --) {
int l = fr(),r = fr(),w = fr();
e[l - 1].push_back({r,w});
}
spfa();
fw(dis[n]);
return 0;
}
标签:fr,int,短路,memset,cnt,flag,dis
From: https://www.cnblogs.com/jingyu0929/p/17566487.html