Task1
搜索出所有的方案
Task2
经过猜测和推理，可以发现每次找到剩下的点中权值最大的点就行,复杂度
O
(
n
2
+
m
)
O(n^2+m)
O(n2+m)
其他的一些未知做法
Task3
由2.1可以轻松得到正解：没必要每次都找一遍权值最大的，只需要对所有点按点权排序后依次删除。复杂度
O
(
n
l
o
g
n
+
m
)
O(nlogn+m)
O(nlogn+m).
其实我们还可以发现没有必要进行真正的排序，对于一条边
(
a
,
b
)
(a,b)
(a,b)，它的贡献一定是
m
i
n
(
a
,
b
)
min(a,b)
min(a,b)
#include<bits/stdc++.h>
#define ll long long
using namespace std
;
const int M
= 1e5+10;
int a
[M
];
ll ans
= 0;
int n
, m
, v
, u
;
int main() {
scanf("%d%d", &n
, &m
);
for(int i
= 1; i
<= n
; i
++)
scanf("%d", &a
[i
]);
for(int i
= 1; i
<= m
; i
++) {
scanf("%d%d", &u
, &v
);
ans
+= min(a
[u
], a
[v
]);
}
printf("%lld", ans
);
return 0;
}
Task1 对于30%的数据 所有菜市位置和小T所在的位置在一条水平直线上
考虑有部分菜市在小T右边，部分菜市在小T左边。 只有两种遍历情况：向左再向右、向右再向左 而在每个点处的、可行的最大体格是确定的，因此直接累加即可。 最终答案在两种情况中选取一个路径更短的或最短路径相同情况下体格和最大的。
Task2 对于s=0且n,m<=50的数据
当
s
=
0
s=0
s=0时，问题转变为从一个点出发遍历
p
p
p个点的最短路问题。 最朴素的想法应该是搜索，每次搜索下一步去哪个点。 但搜索的问题在于它考虑了经过每个点的顺序。 实际上经过顺序不会对答案产生影响、经过了哪些点才会有影响。 因此考虑用状压表示哪些点没去过，然后寻找一个没去过的点更新。 定义状态
d
i
s
[
x
]
[
y
]
[
s
]
dis[x][y][s]
dis[x][y][s] 表示还没去过
s
s
s 集合中的点，目前在点
(
x
,
y
)
(x,y)
(x,y)的最短距离。 可使用bfs更新，复杂度
O
(
n
×
m
×
2
p
)
O(n \times m \times 2^p)
O(n×m×2p) ，可解决
n
,
m
≤
50
n, m \le 50
n,m≤50的情况。
Task3 对于s=0的数据
很容易可以发现，
d
i
s
[
x
]
[
y
]
[
s
]
dis[x][y][s]
dis[x][y][s] 的三维中，
s
s
s在很多点是不会被更新的，因此这些点处出现了状态冗余。 因此只在
p
p
p个点处定义
d
i
s
dis
dis，即状态改为
d
i
s
[
i
]
[
s
]
dis[i][s]
dis[i][s] ，表示在第
i
i
i个点处的最短路。 转移时需要利用两个点间的最短路。 最短路可通过
O
(
p
)
O(p)
O(p) 次bfs预处理得到。
复杂度
O
(
p
×
n
×
m
+
2
p
×
p
2
)
O(p \times n \times m + 2^p \times p^2)
O(p×n×m+2p×p2)
Task4 对于p=1的数据
只有一个目标点，因此只用考虑膨胀问题。
在每一个点都会重新膨胀，因此在每个点处的最大膨胀值其实是固定的。
在bfs的时候直接将每个点的膨胀值加入答案即可。
复杂度
O
(
p
×
n
×
m
+
s
2
×
n
×
m
)
O(p \times n \times m + s^2 \times n \times m)
O(p×n×m+s2×n×m)
Task5 对于100%的数据
将2.3中的bfs部分与2.4结合，即可得到正解。
复杂度
O
(
p
×
n
×
m
+
s
2
×
n
×
m
+
2
p
×
p
2
)
O(p \times n \times m + s^2 \times n \times m+ 2^p \times p^2)
O(p×n×m+s2×n×m+2p×p2)
代码std
#include <bits/stdc++.h>
using namespace std
;
const int N
= 305 , P
= 15 , INF
= 0x3f3f3f3f;
const int dx
[] = {0,0,1,-1} , dy
[] = {1,-1,0,0};
const int fx
[] = {-1,0,1,-1,1,-1,0,1} , fy
[] = {-1,-1,-1,0,0,1,1,1};
struct node
{
int x
,y
;
node
(int X
=INF
,int Y
=-INF
) { x
= X
, y
= Y
; }
friend node
operator + (node x
,node y
) { return node(x
.x
+y
.x
,x
.y
+y
.y
); }
friend bool operator < (node x
,node y
) { return x
.x
== y
.x
? x
.y
> y
.y
: x
.x
< y
.x
; }
} a
[P
+2];
int n
,m
,p
,t
,s
,Map
[N
][N
],c
[N
][N
],d
[N
][N
];
node dis
[P
+2][P
+2],f
[(1<<P
)+2][P
+2],ans
;
int d1
[N
][N
],d2
[N
][N
],v
[N
][N
];
inline int read(void)
{
int x
= 0 , w
= 0; char ch
= ' ';
while ( !isdigit(ch
) ) w
|= ch
== '-' , ch
= getchar();
while ( isdigit(ch
) ) x
= x
* 10 + ch
- 48 , ch
= getchar();
return w
? -x
: x
;
}
inline void input(void)
{
n
= read() , m
= read() , s
= read();
for (int i
=1;i
<=n
;i
++)
for (int j
=1;j
<=m
;j
++)
Map
[i
][j
] = read();
a
[0].x
= read() + 1 , a
[0].y
= read() + 1 , p
= read();
for (int i
=1;i
<=p
;i
++)
a
[i
].x
= read() + 1 , a
[i
].y
= read() + 1;
}
inline bool valid(node p
) { return p
.x
>= 1 && p
.x
<= n
&& p
.y
>= 1 && p
.y
<= m
; }
inline void Bfs(void)
{
queue
< node
> q
;
memset( d
, 0xff , sizeof d
);
for (int i
=1;i
<=n
;i
++)
for (int j
=1;j
<=m
;j
++)
if ( Map
[i
][j
] == 1 )
q
.push( node(i
,j
) ) , d
[i
][j
] = 0;
for (int i
=0;i
<=m
+1;i
++)
q
.push( node(0,i
) ) , q
.push( node(n
+1,i
) ),
d
[0][i
] = d
[n
+1][i
] = 0;
for (int i
=1;i
<=n
;i
++)
q
.push( node(i
,0) ) , q
.push( node(i
,m
+1) ),
d
[i
][0] = d
[i
][m
+1] = 0;
while ( !q
.empty() )
{
node x
= q
.front(); q
.pop();
for (int i
=0;i
<8;i
++)
{
node y
= node( x
.x
+ fx
[i
] , x
.y
+ fy
[i
] );
if ( valid(y
) && d
[y
.x
][y
.y
] == -1 )
{
d
[y
.x
][y
.y
] = d
[x
.x
][x
.y
] + 1;
c
[y
.x
][y
.y
] = min( d
[y
.x
][y
.y
] - 1 , s
);
q
.push( y
);
}
}
}
}
inline void SPFA(node st
)
{
memset( d1
, 0x3f , sizeof d1
);
memset( d2
, 0xcf , sizeof d2
);
memset( v
, 0x00 , sizeof v
);
queue
< node
> q
;
q
.push( node(st
.x
,st
.y
) );
d1
[st
.x
][st
.y
] = 0 , d2
[st
.x
][st
.y
] = c
[st
.x
][st
.y
];
v
[st
.x
][st
.y
] = 1;
while ( !q
.empty() )
{
node x
= q
.front(); q
.pop();
v
[x
.x
][x
.y
] = false;
for (int i
=0;i
<4;i
++)
{
int nx
= x
.x
+ dx
[i
] , ny
= x
.y
+ dy
[i
];
if ( valid(node(nx
,ny
)) && !Map
[nx
][ny
] )
{
if ( d1
[nx
][ny
] > d1
[x
.x
][x
.y
] + 1 )
{
d1
[nx
][ny
] = d1
[x
.x
][x
.y
] + 1;
d2
[nx
][ny
] = d2
[x
.x
][x
.y
] + c
[nx
][ny
];
if ( !v
[nx
][ny
] ) v
[nx
][ny
] = true , q
.push( node(nx
,ny
) );
}
else if ( d1
[nx
][ny
] == d1
[x
.x
][x
.y
] + 1 && d2
[nx
][ny
] < d2
[x
.x
][x
.y
] + c
[nx
][ny
] )
{
d2
[nx
][ny
] = d2
[x
.x
][x
.y
] + c
[nx
][ny
];
if ( !v
[nx
][ny
] ) v
[nx
][ny
] = true , q
.push( node(nx
,ny
) );
}
}
}
}
}
inline void init(void)
{
SPFA( a
[0] );
for (int i
=1;i
<=p
;i
++)
f
[(1<<i
-1)][i
] = node(d1
[a
[i
].x
][a
[i
].y
],d2
[a
[i
].x
][a
[i
].y
]-c
[a
[i
].x
][a
[i
].y
]);
for (int i
=1;i
<=p
;i
++)
{
SPFA( a
[i
] );
for (int j
=1;j
<=p
;j
++)
dis
[i
][j
] = node(d1
[a
[j
].x
][a
[j
].y
],d2
[a
[j
].x
][a
[j
].y
]-c
[a
[j
].x
][a
[j
].y
]);
}
}
inline node
min(node x
,node y
) { return x
< y
? x
: y
; }
inline void DynamicProgram(void)
{
for (int S
=1;S
<1<<p
;S
++)
for (int i
=1;i
<=p
;i
++)
if ( S
>> (i
-1) & 1 )
for (int j
=1;j
<=p
;j
++)
if ( not( S
>> (j
-1) & 1 ) )
f
[S
|(1<<j
-1)][j
] = min( f
[S
|(1<<j
-1)][j
] , f
[S
][i
] + dis
[i
][j
] );
ans
= node( INF
, -INF
);
for (int i
=1;i
<=p
;i
++)
ans
= min( ans
, node(f
[(1<<p
)-1][i
].x
,f
[(1<<p
)-1][i
].y
+c
[a
[i
].x
][a
[i
].y
]) );
}
int main(void)
{
input();
Bfs();
init();
DynamicProgram();
printf("%d %d\n",ans
.x
,ans
.y
);
return 0;
}
Task1
对于每次查询，暴力搜索到
n
n
n的路径。
Task2
注意到每次转移的状态只和当前点
u
u
u 以及从
s
s
s 到当前点经过的所有边的
g
c
d
gcd
gcd的值
g
g
g。
所以很容易可以想到一个
d
p
dp
dp.
定义
d
i
s
[
u
]
[
g
]
dis[u][g]
dis[u][g]为从起点到
u
u
u点，当前经过的所有边的
g
c
d
gcd
gcd 为
g
g
g的最短路。
转移时枚举u点的出边
(
u
,
v
,
w
)
(u,v,w)
(u,v,w)，定义
g
′
=
g
c
d
(
g
,
w
)
g'=gcd(g,w)
g′=gcd(g,w)。则转移方程如下：
d
i
s
[
v
]
[
g
′
]
=
m
i
n
(
d
i
s
[
u
]
[
g
]
+
w
g
′
)
dis[v][g']=min(dis[u][g]+\frac{w}{g'})
dis[v][g′]=min(dis[u][g]+g′w)
由于每个点的状态数只与边的权值的因数有关，故总状态数为$ m \times \sqrt{m}$ 。dp 的转移借助dijkstra 进行，一 次查询的复杂度为
m
×
m
×
log
n
m \times \sqrt{m} \times \log n
m×m
×logn ， Q次查询的复杂度为
Q
×
m
×
m
×
log
n
Q \times m \times \sqrt{m} \times \log n
Q×m×m
×logn（最后一个log 为 dijkstra的复杂度），预计得分 60
Task3
很容易注意到，终点是固定的，所以可以从这里下手。
但是有一点不是很方便，就是边权的定义。但边权只与起点到这条边的 gcd有关，因此可以枚举这个 gcd的值。
定义
d
i
s
[
u
]
[
g
]
dis[u][g]
dis[u][g] 为从
u
u
u 点到终点，从起点到
u
u
u 点的所有路径的
g
c
d
gcd
gcd为
g
g
g。
转移时枚举
v
v
v 点的出边
(
u
,
v
,
w
)
(u,v,w)
(u,v,w),枚举
g
′
g'
g′的倍数g.注意到该转移方程只可在
g
′
∣
w
g'|w
g′∣w 的时候进行转移
d
i
s
[
u
]
[
g
]
=
m
i
n
(
d
i
s
[
v
]
[
g
′
]
+
w
g
′
)
dis[u][g]=min(dis[v][g']+\frac{w}{g'})
dis[u][g]=min(dis[v][g′]+g′w)
虽然需要枚举
g
g
g，但该算法可以
O
(
1
)
O(1)
O(1)地回答每个询问
该算法复杂度为
O
(
m
×
V
×
log
V
+
Q
)
O(m\times V \times \log V +Q)
O(m×V×logV+Q) （最后一个
log
\log
log 为dijkstra 的复杂度），足以通过此题
代码std
#include <bits/stdc++.h>
#define mp make_pair
using namespace std
;
struct Node
{int y
, next
, v
;}e
[4005];
int Link
[1005], t
= 0;
inline void Insert(int x
, int y
, int v
)
{
e
[++ t
].y
= y
;
e
[t
].next
= Link
[x
];
e
[t
].v
= v
;
Link
[x
] = t
;
return;
}
int dis
[1005][505];
bool vis
[1005][505];
int gcd(int a
, int b
){return !b
? a
: gcd(b
, a
% b
);}
int n
, m
;
int C
[1005];
void Dij(int x
)
{
if (C
[x
])
{
printf("%d\n", C
[x
]);
return;
}
int h
= 1, t
= 1;
priority_queue
< pair
< int , pair
< int , int > > > q
;
q
.push(mp(0, mp(x
, 0) ) );
memset(dis
, 0x3f, sizeof(dis
) );
memset(vis
, 0, sizeof(vis
) );
dis
[x
][0] = 0;
while (!q
.empty() )
{
pair
< int , int > Now
= q
.top().second
;
q
.pop();
if (vis
[Now
.first
][Now
.second
])
continue;
vis
[Now
.first
][Now
.second
] = true;
for (int i
= Link
[Now
.first
] ; i
; i
= e
[i
].next
)
{
int d
= gcd(Now
.second
, e
[i
].v
);
if (dis
[Now
.first
][Now
.second
] + e
[i
].v
/ d
< dis
[e
[i
].y
][d
] )
{
dis
[e
[i
].y
][d
] = dis
[Now
.first
][Now
.second
] + e
[i
].v
/ d
;
q
.push(mp(-dis
[e
[i
].y
][d
], mp(e
[i
].y
, d
) ) );
}
}
}
int Ans
= 2e9;
for (int i
= 0 ; i
<= 500 ; ++ i
)
Ans
= min(Ans
, dis
[n
][i
]);
printf("%d\n", Ans
);
C
[x
] = Ans
;
return;
}
int main()
{
scanf("%d%d", &n
, &m
);
for (int i
= 1 ; i
<= m
; ++ i
)
{
int x
, y
, w
;
scanf("%d%d%d", &x
, &y
, &w
);
Insert(x
, y
, w
), Insert(y
, x
, w
);
}
int q
;
scanf("%d", &q
);
for (int i
= 1 ; i
<= q
; ++ i
)
{
int x
;
scanf("%d", &x
);
Dij(x
);
}
return 0;
}
