2020HDU多校第四场–1004–Deliver the Cake(HDU-6805)

题目链接
我是虚假的图论选手,真正的摸鱼选手
HDU/牛客 多校进行到现在第一次赛中切掉图论的题…(一直躺
————————-
题意:
给出

nn

n个村庄,每个村庄有一种特定的属性(

leftleft

left

midmid

mid

rightright

right)

leftleft:

left: 只有把货物放在左手的人才能进入此村庄

right:right:

right: 只有把货物放在右手的人才能进入此村庄

mid:mid:

mid: 把货物放在左手或右手都可以进入此村庄
给出村庄之间的路(双向边),和起点终点,以及把货物在左右手之间交换一次所需的时间,求问从起点到终点最少需要多少时间(你可以自由选择起点时你的状态(左or右),但是你必须要满足这个村庄的属性
也就是说起点为

leftleft

left或者

rightright

right时,你必须要以这个状态出发,为

midmid

mid时你可以任选状态出发
读入
T组样例,每组第一读入五个数

nn

n,

mm

m,

SS

S,

TT

T,

xx

x,分别代表点数,边数,起点,终点,以及切换左右手所需时间
第二行读入一个长度为

nn

n的字符串,每个下标所对应的字符则为这个村庄的属性,分别为

LMRLMR

LMR
之后

mm

m行每行读入三个数

uu

u,

vv

v,

ww

w,代表有一条链接

uu

u和

vv

v的双向边,权值为

ww

w
思路
我想的是拆点+最短路
首先最短路的本质很轻松就可以看出来,点与点之间的权值就是原有权值加上这两点交换左右手的权值,如果需要交换那就是原有权值加上

xx

x就可以了
但是问题是此时有一个

midmid

mid属性不好处理,如果按照前面所说的变成

LL

L到

midmid

mid到

RR

R,那要怎么加权值呢?
所以这个时候就需要采用拆点了,我们可以把所有的点

11

1到

nn

n都拆点拆成

11

1到

nn

n和

n+1n+1

n+1到

n+nn+n

n+n,这样一来就把所有的点都拆成了两部分,左边部分代表

leftleft

left属性的这个点,右边部分代表

rightright

right属性的这个点,同时建立一个超级源点

00

0和超级汇点

n2+1n*2+1

n∗2+1
大致如下(边是瞎连的,主要理解思想
2020HDU多校第四场--1004--Deliver the Cake(HDU-6805)

先连接源点与起点,如果起点是

LL

L,那么就把源点与左部分的起点相连,如果是

RR

R就和右部分的起点相连,如果是

midmid

mid就把左右都和源点连起来
同理连接终点和汇点
同时我们对于给出的

mm

m条边都采取这个方式,枚举一下边

u,vu,v

u,v的所有形式

uu

u有

LMRLMR

LMR,

vv

v有

LMRLMR

LMR,
L就采用左边点与其相连,R就采用右边点与其相连,M就是左右都和对面连上
讲一下样例的连边

1
3 3 1 3 100
LRM
1 2 10
2 3 10
1 3 100

uu

u,

vv

v)=

ww

w
对于第一条边,1,2,10 然后1是L,2是R,所以需要把1的左部分和2的右部分连起来
对于第二条边,2,3,10 ,2是R,3是M,所以要把2的右部分和3的左部分以及右部分连起来
对于第三条边,1,3,19,1是L,3是M,所以要把1的左部分和3的左部分以及右部分连起来,
同时起点是1,终点是3,建立的源点是0,汇点是

32+1=73*2+1=7

3∗2+1=7
那么就把源点和1(L)的左部分连起来,汇点和3(M)的左右部分都连起来
建图就是
2020HDU多校第四场--1004--Deliver the Cake(HDU-6805)
同时关于权值的选择就是,L和R之间的连边需要在原有基础上加上交换左右手所需的

xx

x,所有和源点(

SS

S)汇点(

TT

T)所连的边权值都为0
(因为是虚拟源点和虚拟汇点啊,所以权值为0,这个不懂的就自己找找这个概念和技巧)
所以带上权值的话这个图就是
2020HDU多校第四场--1004--Deliver the Cake(HDU-6805)
那么就是直接跑一个最短路

dijstradijstra

dijstra算法就可以啦(需要堆优化,

1e51e5

1e5
如果有描述错误欢迎指出,点个赞呗hhhhhh
那下面就直接放代码了,以及自己写的的

DijstraDijstra

Dijstra板子,完结撒花啦

const int maxn = 2e5 + 70;
const int maxm = 2e6 + 7;
// 优化查找最近点的优先队列
struct qnode {
int u;
LL w;
qnode(int _u = 0, LL _w = 0) : u(_u), w(_w) {}
bool operator < (const qnode& b) const {
return w > b.w;
}
};
// 储存边以及权值
struct Edge {
int v;
LL w;
Edge(int _v = 0, LL _w = 0) : v(_v), w(_w) {}
};
char str[maxn];
struct Dijstra {
LL dis[maxn];
int n, m, S, T;
int start, end;
LL cc;
bool vis[maxn];
vector<Edge> G[maxn];
priority_queue<qnode> pq;
// 初始化
void init() {
while(!pq.empty()) {pq.pop();}
for(int i = 0; i <= n * 2 + 1; ++ i) {
vis[i] = false;
dis[i] = inf;
G[i].clear();
}
}
// 加边
void add_edge(int u, int v, LL w) {
G[u].push_back(Edge(v, w));
G[v].push_back(Edge(u, w));
}
// 读入
void read_data() {
scanf("%d %d %d %d %lld", &n, &m, &S, &T, &cc);
scanf("%s", str + 1);
start = 0;
end = n * 2 + 1;
init();
if(str[S] == 'L') {
add_edge(start, S, 0);
} else if(str[S] == 'R') {
add_edge(start, S + n, 0);
} else {
add_edge(start, S, 0);
add_edge(start, S + n, 0);
}
if(str[T] == 'L') {
add_edge(end, T, 0);
} else if(str[T] == 'R') {
add_edge(end, T + n, 0);
} else {
add_edge(end, T, 0);
add_edge(end, T + n, 0);
}
while(m --) {
int u, v;
LL w;
scanf("%d %d %lld", &u, &v, &w);
if(str[u] == 'L') {
if(str[v] == 'L') {
add_edge(u, v, w);
} else if(str[v] == 'R') {
add_edge(u, v + n, w + cc);
} else {
add_edge(u, v, w);
add_edge(u, v + n, w + cc);
}
} else if(str[u] == 'R') {
if(str[v] == 'L') {
add_edge(u + n, v, w + cc);
} else if(str[v] == 'R') {
add_edge(u + n, v + n, w);
} else {
add_edge(u + n, v, w + cc);
add_edge(u + n, v + n, w);
}
} else {
if(str[v] == 'L') {
add_edge(u, v, w);
add_edge(u + n, v, w + cc);
} else if(str[v] == 'R') {
add_edge(u, v + n, w + cc);
add_edge(u + n, v + n, w);
} else {
add_edge(u, v, w);
add_edge(u, v + n, w + cc);
add_edge(u + n, v, w + cc);
add_edge(u + n, v + n, w);
}
}
}
}

void dijstra(int st) {
S = st;
dis[st] = 0;
pq.push(qnode(st, 0));
qnode tmp;
while(!pq.empty()) {
tmp = pq.top();
pq.pop();
int u = tmp.u;
if(vis[u]) {
continue;
}
vis[u] = true;
int sz = G[u].size();
for(int i = 0; i < sz; ++ i) {
int v = G[u][i].v;
LL w = G[u][i].w;
if(!vis[v] && dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
pq.push(qnode(v, dis[v]));
}
}
}
printf("%lld\n", dis[end]);
}
}res;
void Solve(int& kase) {
res.read_data();
res.dijstra(0);
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

2020HDU多校第四场--1004--Deliver the Cake(HDU-6805)

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 2020HDU多校第四场–1004–Deliver the Cake(HDU-6805)
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏