Path：
题意：用最少的代价，删除一些边，使得最短路变长。
思路：
https://blog.csdn.net/jerry99s/article/details/96907292（大佬讲得非常好）
我们将所有最短路上的边，建立一张新的图。
以1为源点，n为汇点。求最小割。
这时的最小割即为最小花费（这很显然。）
首先，如何求该条边是最短路上的边。
在牛客某次比赛时做到过思路。
对于边(x,y,z)，dis表示最短路
dis[1-x] + z +dis[x-n]。即满足该边是最短路上的边，（这也很显然）。
那么，先原图跑出1到所有点的最短路。
然后再建反图，跑出n到所以点的最短路。
最后枚举边去建图，然后跑最大流即可。
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef long double ld; typedef pair<LL,int> pii; const int N = 1e4+5; const int M = 5e4+5; const LL Mod = 1e9+7; #define rg register #define pi acos(-1) #define INF 1e18 #define INM INT_MIN #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } int n,m,s,t,cnt = -1; int head[N],dep[N],cur[N]; LL dis1[N],dis2[N]; struct Node{int to;LL dis;int next,st;}e[M<<1],edge[M<<1]; vector<Node> G[N],RG[N]; inline void add(int u,int v,int w) { e[++cnt].to = v,e[cnt].dis = w,e[cnt].next = head[u],head[u] = cnt; e[++cnt].to = u,e[cnt].dis = 0,e[cnt].next = head[v],head[v] = cnt; } bool bfs()//分层 { queue<int> Q; memset(dep,-1,sizeof(dep)); dep[s] = 0; Q.push(s); while(!Q.empty()) { int u = Q.front(); Q.pop(); for(int i=head[u];i!=-1;i=e[i].next) { int y = e[i].to,d = e[i].dis; if(dep[y] == -1 && d > 0) { dep[y] = dep[u]+1; Q.push(y); } } } return dep[t] != -1; } int dfs(int u,int flow) { int nowflow = 0,k; if(u == t) return flow; for(int i=head[u];i!=-1;i=e[i].next) { cur[u] = i;//当前弧优化 int y = e[i].to,d = e[i].dis; if((dep[y] == dep[u]+1) && d > 0) { if(k = dfs(y,min(flow-nowflow,d))) { e[i].dis -= k; e[i^1].dis += k; nowflow += k; if(nowflow == flow) break; } } } if(nowflow == 0) dep[u] = -1;//炸点优化 return nowflow; } LL slove() { LL ans = 0; while(bfs()) { for(int i=1;i<=n;++i) cur[i] = head[i]; ans += dfs(s,INF); } return ans; } void dij(int s,LL *dis,vector<Node> vec[]) { for(int i = 1;i <= n;++i) dis[i] = INF; dis[s] = 0; priority_queue<pii,vector<pii>,greater<pii> > Q; Q.push(pii{dis[s],s}); while(!Q.empty()) { int u = Q.top().second; LL d = Q.top().first; Q.pop(); if(d > dis[u]) continue; for(auto v : vec[u]) { if(dis[v.to] > dis[u]+v.dis) { dis[v.to] = dis[u]+v.dis; Q.push(pii{dis[v.to],v.to}); } } } } int main() { int ca;ca = read(); while(ca--) { n = read(),m = read(); memset(head,-1,sizeof(head)); cnt = -1; for(int i = 1;i <= n;++i) G[i].clear(),RG[i].clear(); for(int i = 1;i <= m;++i) { int x,y,z; x = read(),y = read(),z = read(); edge[i].st = x,edge[i].to = y,edge[i].dis = z; G[x].push_back(Node{y,z}); RG[y].push_back(Node{x,z}); } dij(1,dis1,G); dij(n,dis2,RG); for(int i = 1;i <= m;++i) { int x = edge[i].st,y = edge[i].to,z = edge[i].dis; if(dis1[x]+dis2[y]+z == dis1[n]) add(x,y,z); } s = 1,t = n; LL ans = slove(); printf("%lld\n",ans); } system("pause"); return 0; }
Vacation
思路1：可二分：二分时间，然后判断这个时间里所有的车能不能都过。（注意不能超车）
思路2：
对于0号车的状态：
无非为两种，始终不会贴前面的车，那么为s0/v0.
会贴着前面的车，那么这时的最大时间为(L0+s1)/v1。
同时前面的车又会贴着前面的车，那么为(L1+s2)/v2。
答案即为其中的最大值。
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef long double ld; typedef pair<LL,int> pii; const int N = 1e5+5; const int M = 5e4+5; const LL Mod = 1e9+7; #define rg register #define pi acos(-1) #define INF 1e18 #define INM INT_MIN #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } int L[N],s[N],v[N]; int main() { int n; while(~scanf("%d",&n)) { for(int i = 0;i <= n;++i) L[i] = read(); for(int i = 0;i <= n;++i) s[i] = read(); for(int i = 0;i <= n;++i) v[i] = read(); LL sum = 0; double ans = (1.0*s[0])/v[0]; for(int i = 1;i <= n;++i) { sum += L[i]; ans = max(ans,(1.0*(sum+s[i]))/v[i]); } printf("%.12f\n",ans); } system("pause"); return 0; }