admin 管理员组文章数量: 1087677
补题（最短路+拆点）HUD
.php?pid=6805
题意：有n个村庄，m条无向道路，道路单位为米，张三现在要拿着蛋糕从s村庄走到t村庄，村庄分为L M R三种类型。L村庄只能左手拿蛋糕，R村庄只能右手拿蛋糕，M村庄左右手拿都行，每次更换左右手必须停下耗费x秒的时间，现在要你求从s走到t的最短时间，速度看成1s/m。
刚开始思路：不考虑换手那就是最短路模板了，这题难点在于走的过程中不知道什么时候换手是最优解，我刚开始的做法是跑spfa，在更新路径的时候同时记录当前是哪只手提蛋糕（类似与bfs跑一个图时用结构体数组作队列记录路劲），TLE后就不知道怎么处理了
正解：将换手所耗费的时间转化为边权，只要将所有换手的情况都转化为边权，就不需要你考虑何时换手是最优解，跑一边dijs模板就行了
那怎么转化呢，我们先思考一条边上的两个点u和v有哪些组合情况，答案是3*3=9种（LL，LR，RL，RR，LM，ML，MR，RM，MM）前四种情况的边权是很好处理的，LL和RR正常连边，LR和RL就在u—v这条边权上加上x，
不好处理的是含M的情况，因为在前四种情况中你知道，当前不用换手（RR，LL），当前必须换手（LR，RL），但在含M时你不知道当前是否需要换手，不好处理M那就将M拆成L和R
拆点
将一个M点拆为一个R点和一个L点，例如LM这种情况就转化为了LL和LR这两种情况，RM就转化为RR和RL，MM则转化为RR，RL，LL，LR。转化后的连边情况都变成了上面好处理4种情况，然后就是跑dijs模板了。
代码：
#include<bits/stdc++.h>
using namespace std;
long long dis[1000005],vis[500005];//跑dijs的距离数组和标记数组struct my{
int to;
long long cmp;//cmp是权值,rev记录to到from边在to表的位置
};
int n,m;//n个点m条边设为全局变量，其他设为局部变量（这样在多次跑dijs初始化时更不会出错）
int b[1000005];
char c[1000005];
typedef pair<long long,int> P;//priority_queue<P,vector<P>,greater<P> > qque;
vector<my> e[500005];
void add_e(int from,int to,long long cmp)//加一条from到to权值为cmp的边，并且反向存to到from权值为0的边
{e[from].push_back((my){to,cmp});e[to].push_back((my){from,cmp});
}
void init()
{int N=2*n+5;for(int i=0;i<=N;i++){e[i].clear();b[i]=0;c[i]=0;dis[i]=0x3f3f3f3f3f3f3f3f;vis[i]=0;}// while(!qque.empty())//qque.pop();
}
void print(int s,int t,int x)
{int t1,t2;long long t3;scanf("%s",c);for(int i=0;i<n;i++){if(c[i]=='L')b[i+1]=1;else if(c[i]=='M')b[i+1]=2;else if(c[i]=='R') b[i+1]=3;}for(int i=0;i<m;i++){scanf("%d%d%lld",&t1,&t2,&t3);if(b[t1]==1&&b[t2]==3)add_e(t1,t2,t3+x);else if(b[t1]==3&&b[t2]==1)add_e(t1,t2,t3+x);else if(b[t1]==2&&b[t2]==1)add_e(t1,t2,t3),add_e(n+t1,t2,t3+x);else if(b[t2]==2&&b[t1]==1)add_e(t1,t2,t3),add_e(t1,n+t2,t3+x);else if(b[t1]==3&&b[t2]==2)add_e(t1,t2,t3+x),add_e(t1,n+t2,t3);else if(b[t1]==2&&b[t2]==3)add_e(t1,t2,t3+x),add_e(t1+n,t2,t3);else if(b[t1]==2&&b[t2]==2)add_e(t1,t2,t3),add_e(t1+n,t2+n,t3),add_e(t1,t2+n,t3+x),add_e(t1+n,t2,t3+x);else if(b[t1]==1&&b[t2]==1)add_e(t1,t2,t3);else if(b[t1]==3&&b[t2]==3) add_e(t1,t2,t3);}
//if(b[s]==2)add_e(0,s+n,0),add_e(0,s,0);
//if(b[t]==2)add_e(2*n+1,n+t,0);add_e(2*n+1,t,0);
}void dij(int s,int t)
{priority_queue<P,vector<P>,greater<P> > qque;dis[s]=0;
qque.push(P(0,s));
int u,v,sizee;
long long ccmp;
while(!qque.empty()){P p=qque.top();u=p.second;qque.pop();//if(dis[u]<p.first) continue;//两种方式判断是否需要通过当前点去更新路径，这种方式可以省一个标记数组if(vis[u]==1) continue;//只通过每个点一次更新路径就行了，重复去更新可能会超时//if(u==t) break;//到通过t点更新时，已经找到了最小的dis【t】，可以提前结束vis[u]=1;sizee=e[u].size();for(int i=0;i<sizee;i++){v=e[u][i].to;ccmp=e[u][i].cmp;if(dis[v]>dis[u]+ccmp){dis[v]=dis[u]+ccmp;qque.push(P(dis[v],v));}}}}int main()
{int s,t,fre,x;cin>>fre;while(fre--){scanf("%d%d%d%d%d",&n,&m,&s,&t,&x);init();//初始化print(s,t,x);//输入边（建图）dij(0,2*n+1);//传入源点和汇点printf("%lld\n",dis[2*n+1]);}
}
本文标签： 补题（最短路拆点）HUD
版权声明：本文标题：补题（最短路+拆点）HUD 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1694393249a251538.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论