利用这一篇博客记录图论中一类典型题的解题记录-分层图
1.P4822 [BJWC2012]冻结
problem4822
解法1- spfa+两个队列维护答案
从与起点相连的每条边开始遍历，一个队列用于维护每次实行松弛操作更新的点，另一个队列维护当前这个点使用的冻结次数，用dist[j][card]表示从起点到j这一点使用card次冻结后的最短距离，然后不断更新答案即可。
解法1-代码
#include <bits/stdc++.h>
using namespace std;
const int N = 60, M = 2e3+100;
int h[N],e[M],w[M],ne[M],idx;
int dist[N][N];
int n,m,k;
queue<int> q;
queue<int> q_sc;
bool st[N][N]; //st[i][j] 表示到第i个点的最短路径使用了j次冻结的状态是否在队列中
void add(int a,int b,int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a],h[a] = idx++;
}
void spfa(){
q.push(1);
q_sc.push(0);
memset(dist,0x3f,sizeof dist);
// for(int i = 0; i<=k; i++) dist[1][i] = 0;
dist[1][0] = 0;
st[1][0] = true;
while(!q.empty()){
int t = q.front(), card = q_sc.front();
q.pop(),q_sc.pop();
st[t][card] = false;
for(int i = h[t]; ~i; i = ne[i]){
int j = e[i];
//不使用冻结
if(dist[j][card] > dist[t][card] + w[i]){
dist[j][card] = dist[t][card] + w[i];
if(!st[j][card]){
q.push(j);
st[j][card] = true;
q_sc.push(card);
}
}
//使用冻结
if(dist[j][card+1] > dist[t][card] + w[i]/2){
dist[j][card+1] = dist[t][card] + w[i]/2;
if(!st[j][card+1] && card<k){
q.push(j);
st[j][card+1] = true;
q_sc.push(card+1);
}
}
}
}
}
int main()
{
cin>>n>>m>>k;
memset(h,-1,sizeof h);
while(m--){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
spfa();
// cout<<dist[4][0] << " " << dist[4][1]<<endl;
int ans = 1e9;
for(int i = 0; i<=k; i++){
ans = min(ans,dist[n][i]);
}
cout<<ans;
return 0;
}
解法2-分层图
对于分层图个人理解就是，每一层的所有节点之间边的权值与第0层的一致，但每一层之间边的权值不相同，假设在第i层有u，v两点，u到v的代价是w，那么在第i+1层的u'和v'之间的权值也为w，但u与v' 以及 v 与 u'的权值在这一题中就为w/2， 也就是在同层之间旅行，边权的代价不变，但是在不同层之间旅行，边权就会按照题意发生变化，所以一旦分层图建图完毕，在分层图上跑最短路，就能得到这一类问题的答案，另外，对一般分层图的数据范围来说，k的值会给得很小，从下面两题也可以看出来。
解法2-代码
#include <bits/stdc++.h>
using namespace std;
const int N = 60*600, M = 2e5+100;
int h[N], e[M],ne[M],w[M],idx;
int n,m,k;
bool st[N];
int dist[N];
void add(int a,int b,int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a],h[a] = idx++;
}
void spfa(){
memset(dist,0x3f,sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while(!q.empty()){
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; ~i; i = ne[i]){
int j = e[i];
if(dist[j] > dist[t] + w[i]){
dist[j] = dist[t] + w[i];
if(!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
}
int main()
{
cin>>n>>m>>k;
memset(h,-1,sizeof h);
while(m--){
int x,y,c;
cin>>x>>y>>c;
for(int i = 0; i<=k; i++){
//第i层
add(x+i*n,y+i*n,c);
add(y+i*n,x+i*n,c);
if(i<k){
add(x+i*n,y+(i+1)*n,c/2);
add(y+i*n,x+(i+1)*n,c/2);
}
}
}
spfa();
int ans = 1e9;
for(int i = 1; i<=k+1; i++){
ans = min(ans,dist[i*n]);
}
cout<<ans;
return 0;
}
2.P2939 [USACO09FEB]Revamping Trails G
problem2939
分析
一样的思路，只不过这里用dijkstra来跑最短路。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 20*100000, M = 5e4*4*30;
int h[N], e[M],w[M],ne[M],idx;
int n,m,k;
int dist[N];
bool st[N];
typedef pair<int,int> PII;
void add(int a,int b,int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> q;
q.push({0,1});
while(!q.empty()){
auto a = q.top();
q.pop();
int t = a.second, distance = a.first;
if(st[t]) continue;
st[t] = true;
for(int i = h[t]; ~i; i = ne[i]){
int j = e[i];
if(dist[j] > distance + w[i]){
dist[j] = distance + w[i];
q.push({dist[j],j});
}
}
}
}
int main()
{
cin>>n>>m>>k;
memset(h,-1,sizeof h);
while(m--){
int a,b,c;
cin>>a>>b>>c;
for(int i = 0; i<=k; i++){
add(a+i*n,b+i*n,c);
add(b+i*n,a+i*n,c);
if(i<k){
add(a+i*n,b+(i+1)*n,0);
add(b+i*n,a+(i+1)*n,0);
}
}
}
dijkstra();
int ans = 1e9;
for(int i = 1; i<=k+1; i++){
ans = min(ans,dist[n*i]);
}
cout<<ans;
return 0;
}
3.P4568 [JLOI2011]飞行路线
problem4586
分析
与第二题代码除了数据范围不一样，其他同。
代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 2e6+100, M = 1e7+100;
int n,m,k,s,td;
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
bool st[N];
void add(int a,int b,int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[s] = 0;
priority_queue<PII,vector<PII>,greater<PII>> heap;
heap.push({0,s});
while(!heap.empty()){
PII a = heap.top();
heap.pop();
int t = a.second, distance = a.first;
if(st[t]) continue;
st[t] = true;
for(int i = h[t]; ~i; i = ne[i]){
int j = e[i];
if(dist[j] > w[i] + distance){
dist[j] = w[i] + distance;
heap.push({dist[j],j});
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
scanf("%d%d",&s,&td);
// s++, td++;
memset(h,-1,sizeof h);
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
// a++, b++;
for(int i = 0; i<=k; i++){
add(a+i*n,b+i*n,c);
add(b+i*n,a+i*n,c);
if(i<k){
add(a+i*n,b+(i+1)*n,0);
add(b+i*n,a+(i+1)*n,0);
}
}
}
dijkstra();
int ans = 1e8;
for(int i = 0; i<=k; i++){
ans = min(ans,dist[td+i*n]);
// cout<<i<<" "<<dist[i*td]<<endl;
}
cout<<ans<<endl;
return 0;
}
网友评论