分时最短路+次小生成树+最小费用最大流题解

问题 A: 高速

时间限制: 1 Sec 内存限制: 128 MB
提交: 15 解决: 4
[提交][状态][讨论版][命题人:qianyouyou]

题目描述

教练开车去东北,因为比赛地点在东北。共有 n 座城,已知教练在 s 城,比赛地点在 t 城,n 座城之间共有 m 条高速,每条高速连接两座城市,每两座城市之间最多两条高速。每条高速都有权值 v,表示两个城市之间最快可以 v 小时到达。

然而高速不是永久开放的,每条高速都会有一段开放时间 [ a,b ],表示该高速在 a ~ b 小时范围之间开放,其余时间处于关闭状态,不能通过任何车辆。例如 [ 24,27 ]表示该路在第 24 小时到 27 小时之间开放。

已知教练在 0 时刻出发,他最快多少小时可以到达 t 城。

(PS:由于刹车坏掉了,因此车一旦启动就不能停下来,也就是说车不能停于某点或某边,不过车可以来回无限次在两地之间穿梭)

输入

多组测试样例,首行输入 t,表示 t 组样例。

图为无向图,s 城固定为 1 点,t 城固定为 n 点。

每组样例第 1 行,输入n,m(1 < n ≤ 100,0 < m ≤ 1000)。

接下来 m 行,每行 5 个数值x,y,v,l,f。表示 x 与 y 有一条高速,耗时为 v。该路开放时间为[ l,f ]。

数据保证教练可以到达终点,只不过是时间问题。

输出

输出一个数值,即最少耗时。

样例输入

1
2
3
4
5
6
1
5 4
2 3 1 5 11
2 5 1 3 18
4 3 1 7 14
1 4 1 0 15

样例输出

1
10

tag:图论、分时最短路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
//最短路
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 0x3f3f3f3f;
const int maxn = 1e5+7;
int t,n,m,cnt;
int dis[maxn]; //当前该点到原点最短距离
bool vis[maxn]; //是否访问过
int head[maxn]; //点集
struct EDGE{
int next,to,w,l,r; //上一条边,下一个点,权值,左值,右值
}edge[2*maxn]; //边集
struct NODE{
int u,dis;
NODE(){}
NODE(int u,ll w):u(u),dis(w){}
bool operator <(const NODE &a)const{
return dis>a.dis;
}
}node[2*maxn]; //点集加最短距离
void add(int u, int v, int w, int l,int r){ //构建边集
edge[cnt].next = head[u];
edge[cnt].to = v;
edge[cnt].w = w;
edge[cnt].l = l;
edge[cnt].r = r;
head[u] = cnt;
cnt++;
}
void init(){ //初始化
cnt = 0;
memset(head,-1,sizeof(head));
memset(dis,maxx,sizeof(dis));
memset(vis,false,sizeof(vis));
}
void read(){ //读入数据
int u,v,w,l,r;
scanf("%d%d",&n,&m);
for(int i = 0;i < m; i++){
scanf("%d%d%d%d%d",&u,&v,&w,&l,&r);
add(u,v,w,l,r);
add(v,u,w,l,r);
}
}
void init_data(int kk){ //初始化数据
vis[kk] = false;
dis[kk] = maxx;
}
int solve(int s){
priority_queue<NODE>q; //储存最短距离
q.push(NODE(s,0)); //读入原点
while(!q.empty()){ //队列为空则无法到达
int kk = q.top().u; //储存当前最短距离下标
int minD = q.top().dis; //储存当前最短距离
q.pop();
if(kk==n) //若下标为目标值,return
return minD;
vis[kk] = true; //该点是否访问
for(int l = head[kk]; l!=-1; l=edge[l].next){ //松弛边
if(!vis[edge[l].to]&&minD<=edge[l].r&&minD>=edge[l].l&&minD + edge[l].w < dis[edge[l].to]){
dis[edge[l].to] = minD + edge[l].w;
q.push(NODE(edge[l].to,dis[edge[l].to])); //将松弛后的边压入队列
}
}
init_data(kk); //初始化数据
}
return 0;
}
int main(){
scanf("%d",&t);
while(t--){
init(); //初始化
read(); //读入
printf("%d\n",solve(1)); //解决方案
}
return 0;
}

问题 C: 千年老二

时间限制: 1 Sec 内存限制: 128 MB
提交: 24 解决: 12
[提交][状态][讨论版][命题人:qianyouyou]

题目描述

雷婷与万钧是青梅竹马,无论是考试还是玩游戏,雷婷总是第一,而万钧总是第二,尽管万钧有做第一的实力,但他每次都会把第一让给雷婷,仅因为每次读榜单时雷霆万钧听起来是那么顺耳。这天,雷婷参加了 acm 选拔,万钧也跟着雷婷参加。题目是这样的:

有 n 个节点,编号为 1~n,有 m 条边,每条边都有一个距离。两点之间最多只有 1 条边。现在你需要选取 n-1 条边,使得所有点都连接起来都有通路。n-1 条边距离之和越小分数越高。

万钧立马意识到这道题是求最小生成树的,并且每个人的答案不能相同,万钧根据瞪眼法立马瞪出了答案,然而他还是等待雷婷先做完。现在雷婷已经找到了距离最短的1种方案,不过他俩太心有灵犀了,答案一模一样,万钧想获得第 2 名,请你帮万钧想一种方案,距离之和越短越好,但不能和雷婷的结果相同。一条边不同即可认为不同。如果找不到输出 -1。当然存在一种情况,如果雷婷的方案是没有方案求出最短距离,即表示该图没有最小生成树,即输出 -1。总之雷婷的方案是最优解的一种。

输入

存在多组数据,第一行一个正整数 t,表示有 t 组数据。

每组数据第一行有两个整数 n 和 m(2 ≤ n ≤ 100,1 ≤ m ≤ 1000),之后 m 行,每行三个正整数 s,e,w,表示 s 到 e 的双向路的权值为 w。

输出

输出次小生成树的值(如果存在多个最小生成树或仅有一个树,则次小生成树就是最小生成树,输出-1),如果不存在输出 -1。

样例输入

1
2
3
4
5
1
3 3
3 1 3
1 2 1
2 3 2

样例输出

1
4

tag:图论、次小生成树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
//次小生成树
#include<bits/stdc++.h>
using namespace std;
const int L=1e5+7;
const int inf=0x3f3f3f3f;
const int maxn=1000+7;
int father[maxn],n,m,num[maxn],nPos; //父节点(并查集),点数,边数,最小生成树点集,当前访问方位
struct node{
int s,y,w;
}edge[L]; //边集,左端点,右端点,权值
void init(){ //初始化并查集
for(int i=0;i<=n;i++)
father[i]=i;
}
int root(int x){ //并查集,构造父节点
return father[x]==x?x:father[x]=root(father[x]);
}
void unite(int x,int y){ //并查集,合并两个联通图
x=root(x);
y=root(y);
if(x!=y)
father[y]=x;
}
int alike(int x,int y){ //并查集,判断是否为同一连通图
return root(x)==root(y);
}
int cmp(node a,node b){ //sort结构体排序
return a.w<b.w;
}
int secondTree(int pos) //次小生成树
{
init(); //初始化
int sum=0,cnt=0;
for(int i=0;i<m;i++) //对于删去边后的图进行最小生成树运算
{
if(cnt==n-1)
break;
if(i==pos)
continue;
if(!alike(edge[i].s,edge[i].y)){
unite(edge[i].s,edge[i].y);
sum+=edge[i].w;
cnt++;
}
}
return cnt!=n-1?-1:sum; //判断删除边后是否能构成最小生成树
}
int kruskal(){ //最小生成树
init();
sort(edge,edge+m,cmp); //对边进行权值排序
int sum=0,cnt=0;
for(int i=0;i<m;i++) //每次选择最小且未访问过的一条边
{
if(cnt==n-1)
break;
if(!alike(edge[i].s,edge[i].y)){
unite(edge[i].s,edge[i].y);
sum+=edge[i].w;
cnt++;
num[++nPos]=i;
}
}
return cnt!=n-1?-1:sum; //判断边是否大于等于n-1,否则输出-1
}
void read(){ //读入数据
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
scanf("%d%d%d",&edge[i].s,&edge[i].y,&edge[i].w);
}
void solve(){ //解决方案
int Min=inf;
nPos=0;
int mst=kruskal(); //最小生成树值
if(mst==-1) { //没有最小生成树即输出-1
printf("-1\n");
return;
}
for(int i=1;i<=nPos;i++){ //对最小生成树的每条边进行遍历,选择删边后的最小值
int secmst=secondTree(num[i]);
if(secmst!=-1) //若没有次小生成树输出-1
Min=min(Min,secmst);
}
if(Min!=inf&&Min!=mst)
printf("%d\n",Min); //输出结果
else
printf("-1\n");
}
int main(){
int t;
scanf("%d",&t);
while(t--){
read(); //读入数据
solve(); //解决方案
}
return 0;
}

问题 F: 给力台球厅

时间限制: 1 Sec 内存限制: 128 MB
提交: 10 解决: 3
[提交][状态][讨论版][命题人:qianyouyou]

题目描述

教练爱打台球。这天偶遇一家台球厅,便进去看看。然而这家台球厅貌似和平常的台球厅不太一样,它的每张桌面上的洞都是随机分布在桌面上的,球也是随机摆放的。

教练立即意识到,此台球厅的桌面不符合正态分布之概率密度函数,而是呈离散分布,顿时患有强迫症的教练心里就不舒服了。为了平缓一下翻腾的内心,教练随机选取了一张球和洞数量一样的球桌,望着奇怪的桌面与奇怪的球,教练脑袋上不禁长出了大把大把的草:如果能求出所有球入洞的最短距离之和该有多好啊。

现有一个桌面面积为 n×m 的台球桌,将台球桌分成 n×m 个小格,台球桌上有许多的洞和许多的球,均匀分布在小格里,且每个小格只有三种状态,有球,有洞,空白。球用 @ 表示,洞用 # 表示,空白的地方用 * 表示。每个洞只能容纳一个球,球每次只能按照上下左右的方向移动,且每移动一格视为移动 1 个单位长度。当一个球被另一个球挡住时,它可以跳球,所以每一个球都可以完全无视其他球或洞的存在而继续前行,直到进自己心仪的洞。现求所有球进洞的距离之和最小是多少。如果你能帮教练解决这道题,恭喜你就是 ACM 队员了(每个球只能进一个洞,每个洞内有球的话就变成空白状态)

输入

多组测试样例,首行输入 m,n,即矩形台球桌面的边长。(2 ≤ m,n ≤ 20,球最多100个,洞最多100个,保证洞和球数量相等)

输出

输出一个整数,即所有球入洞的距离最短是多少。

样例输入

1
2
3
4
5
6
7
8
9
10
11
2 2
*#
@*
7 8
****#***
****#***
****#***
@@@@#@@@
****#***
****#***
****#***

样例输出

1
2
2
28

tag:图论、最小费用最大流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
//网络流
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f; //无穷大
const int maxn = 60007;
const int maxm = 1000007;
int vis[maxn],d[maxn],pre[maxn],a[maxn],m,n; //是否访问,最短路,前置节点,流量,边集,点集
char mp[107][107]; //台球地图
struct Edge{
int u, v, c, cost, next;
}edge[maxm]; //网络流边集

int s[maxn], cnt; //每个点流量

void init(){ //初始化
cnt = 0;
memset(s, -1, sizeof(s));
}

void add(int u, int v, int c, int cost){ //对两点之间进行单向边建立
edge[cnt].u = u;
edge[cnt].v = v;
edge[cnt].cost = cost;
edge[cnt].c = c;
edge[cnt].next = s[u];
s[u] = cnt++; //建立单向边
edge[cnt].u = v;
edge[cnt].v = u;
edge[cnt].cost = -cost;
edge[cnt].c = 0;
edge[cnt].next = s[v];
s[v] = cnt++; //建立双向边
}

bool spfa(int ss, int ee,int &flow,int &cost){ //以距离为费用寻找最短路,以最短路为当前增广路
queue<int> q;
memset(d, INF, sizeof d);
memset(vis, 0, sizeof vis); //初始化
d[ss] = 0, vis[ss] = 1, pre[ss] = 0, a[ss] = INF;
q.push(ss);
while (!q.empty()){ //spfa以费用为距离寻找最短路
int u = q.front();q.pop();
vis[u] = 0;
for (int i = s[u]; ~i; i = edge[i].next){ //和当前点相连所有边松弛过程
int v = edge[i].v;
if (edge[i].c>0&& d[v]>d[u] + edge[i].cost){ //松弛过程
d[v] = d[u] + edge[i].cost;
pre[v] = i;
a[v] = min(a[u], edge[i].c); //取最小值
if (!vis[v]){
vis[v] = 1;
q.push(v); //压入待松弛队列
}
}
}
}
if (d[ee] == INF) return 0; //判断是否有最短路,无说明最大流完成
flow += a[ee];
cost += d[ee]*a[ee];
int u = ee;
while (u != ss){ //求当前最短路下的流量和
edge[pre[u]].c -= a[ee];
edge[pre[u] ^ 1].c += a[ee];
u = edge[pre[u]].u;
}
return 1;
}

int MCMF(int ss, int ee){ //最小费用最大流
int cost = 0, flow=0; //初始化
while (spfa(ss, ee, flow, cost)); //寻找增广路径,直到没有增广路径为止
return cost; //返回最大流费用
}

struct point{
int x,y; //球坐标,洞坐标
};

void solve(){
point H[107],P[107]; //建立球集与洞集
int h=0,p=0;
for(int i=0;i<n;i++){ //输入地图
scanf("%s",&mp[i]);
for(int j=0;j<m;j++){
if(mp[i][j]=='#'){ //若为洞则坐标加入洞集
H[h].x=i;
H[h].y=j;
h++;
}
else if(mp[i][j]=='@'){ //若为球则坐标加入球集
P[p].x=i;
P[p].y=j;
p++;
}
}
}
init(); //初始化
for(int i=0;i<h;i++)
for(int j=0;j<p;j++){
int c=fabs(H[i].x-P[j].x)+fabs(H[i].y-P[j].y);
add(i+1,h+j+1,1,c);
} //建立球与洞之间的路径
for(int i=0;i<h;i++) //建立超级源点
add(0,i+1,1,0);
for(int i=0;i<p;i++) //建立超级汇点
add(h+1+i,h+p+1,1,0);
printf("%d\n",MCMF(0,h+p+1)); //最小费用最大流
}

int main(){
while(~scanf("%d%d",&n,&m)){
if(!(m||n))
break;
solve(); //解决方案
}
return 0;
}

文章结束了,但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!