0%

2019 Multi-University Training Contest 1

Problem D.Vacation

地址

题意

​ n+1辆车,每辆车有个位置$s[i]$,长度$l[i]$和速度$v[i]$,求第一辆车到达终点的时间。
有几点比较重要:

  • 首先题面说了道路狭窄,一次只能通过一辆车,也就是不能超车,即使你速度快的飞起。
  • 还有就是一辆车到了$stop-line$以后还是以同样的速度行驶。

题解

因为前面车的速度不受后面车的影响,那么我们就分别求从1到n+1​车前面没车的时间,那么1车最终的时间肯定是这n+1个时间重最大的那个时间。

代码如下

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
#include<iostream>
#include<map>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<climits>
#include<algorithm>
#include<cmath>
#include<climits>
#include<queue>
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
const int maxn=1e5+10;
double l[maxn],s[maxn],v[maxn],suml[maxn];
int main(){
int n;
while(~scanf("%d",&n)){
for(int i=1;i<=n+1;i++) scanf("%d",&l[i]),suml[i]=suml[i-1]+l[i];
for(int i=1;i<=n+1;i++) scanf("%d",&s[i]);
for(int i=1;i<=n+1;i++) scanf("%d",&v[i]);
double ans=0;
for(int i=1;i<=n+1;i++) ans=max(ans,(s[i]+suml[i]-l[1])/v[i]);
printf("%.10f\n",ans);
}
}

Problem E. Path

地址

题意:

​ 就是有一个n个节点,m条边的图,让你删去一些边使得从1到n的最短路变长。

题解:

​ 刚开始看这题时就是先求的最短路,然后枚举每个最短路,求这些最短路的最短边的和,显然,肯定是超时。

​ 比完赛知道了原来有最小割(最大流)这个东西,最小割可以这样理解:比如在一堆水管网络(这些水管的尺寸不同,也就是capacity容量不同)中,从起点到终点最大可以通过的水量。前面这句话可能不严谨,但是道理就是这样的。

于是我先用$Dijkstra$求出了最短路,然后根据公式$dist[u]+dis[u][v]==dis[v]$,也就是用最短路算法求出来的dist数组和各个边的长度来判断这个边是否在最短路径上。如果在最短路径上就把这个边加到新图中,然后用刘汝佳书上的dinik模版算一下最大流。

代码如下:

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include<iostream>
#include<map>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<climits>
#include<algorithm>
#include<cmath>
#include<climits>
#include<queue>
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
const int maxn=1e4+10;
const int inf=0x3f3f3f3f;
#define LL long long
struct edge{
LL from,to,cap,flow;
edge(){}
edge(LL from,LL to,LL cap,LL flow):from(from),to(to),cap(cap),flow(flow){}
};
struct dinic{
LL n,m,s,t;
vector<edge> edges;
vector<int > G[maxn];
bool vis[maxn];
LL cur[maxn];
LL d[maxn];

void addedge(LL from,LL to,LL cap){
edges.push_back(edge(from,to,cap,0));
edges.push_back(edge(to,from,0,0));
m=edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}

bool bfs(){
memset(vis,0,sizeof(vis));
queue <int> Q;
Q.push(s);
d[s]=0;
vis[s]=1;
while(!Q.empty()){
LL x=Q.front();
Q.pop();
for(LL i=0;i<G[x].size();i++){
edge &e=edges[G[x][i]];
if(!vis[e.to]&&e.cap>e.flow){
vis[e.to]=1;
d[e.to]=d[x]+1;
Q.push(e.to);
}
}
}
return vis[t];
}
LL dfs(LL x,LL a){
if(x==t||a==0) return a;
LL flow=0;
LL f;
for(LL &i=cur[x];i<G[x].size();i++){
edge &e=edges[G[x][i]];
if((d[e.to]==d[x]+1)&&(f=dfs(e.to,min(e.cap-e.flow,a)))>0){
e.flow+=f;
edges[G[x][i]^1].flow-=f;
flow+=f;
a-=f;
if(a==0) break;
}
}
return flow;
}

LL maxflow(LL a,LL b){
s=a;t=b;
LL flow=0;
while(bfs()){
memset(cur,0,sizeof(cur));
flow+=dfs(s,inf);
}
return flow;
}
};


struct node{
LL v,c;
node(){}
node(LL v,LL c):v(v),c(c){}
bool operator<(const node & rhs)const{
return c>rhs.c;
}
};
struct Edge{
LL v,cost;
Edge(int v,int cost):v(v),cost(cost){}
};
struct Dij{
LL dist[maxn];
int vis[maxn];
vector<Edge>E[maxn];
void Dijkstra(int s,int n){
memset(vis,0,sizeof vis);
memset(dist,inf,sizeof dist);
dist[1]=0;
priority_queue<node>pq;
pq.push(node(s,0));
node tmp;
while(!pq.empty()){
tmp=pq.top();
pq.pop();
LL cur=tmp.v;
if(vis[cur]) continue;
vis[cur]=1;
for(LL i=0;i<E[cur].size();i++){
LL v=E[cur][i].v;
LL dis=E[cur][i].cost;
if(!vis[v]&&dist[v]>dist[cur]+dis){
dist[v]=dist[cur]+dis;
pq.push(node(v,dist[v]));
}
}
}
dinic D;
for(LL i=1;i<=n;i++){
for(int j=0;j<E[i].size();j++){
LL v=E[i][j].v;
LL dis=E[i][j].cost;
if(dist[i]+dis==dist[v]){
D.addedge(i,v,dis);
}
}
}
cout<<D.maxflow(1,n)<<endl;
}
};

int main(){
int T;
scanf("%d",&T);
while(T--){
LL n,m;
scanf("%d%d",&n,&m);
LL u,v,c;
Dij Di;
for(LL i=0;i<m;i++){
scanf("%d%d%d",&u,&v,&c);
Di.E[u].push_back(Edge(v,c));
}
Di.Dijkstra(1,n);
}
return 0;
}