T1
枚举流量对于花费跑 dijkstra 并取比值的 \(\max\) 即可。
关于为什么枚举流量不一定当前最优的问题，因为最优解的流量总在枚举范围内，所以无需考虑当前是否最优。
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
int dis[100031];
bool vis[100031];
struct Edge{ int v,c,f; };
vector<Edge> G[200031];
struct Node{
int u,c,f;
bool operator < (const Node &b) const{
return c>b.c;
}
};
void dijkstra(int s,int x){
memset(vis,0,sizeof(vis));
memset(dis,0x3f,sizeof(dis)),dis[s]=0;
priority_queue<Node> pq; pq.push({s,0});
while(!pq.empty()){
Node now=pq.top(); pq.pop();
if(vis[now.u]) continue; vis[now.u]=1;
for(auto i:G[now.u]){
if(i.f>=x&&dis[i.v]>dis[now.u]+i.c)
dis[i.v]=dis[now.u]+i.c,
pq.push({i.v,dis[i.v]});
}
}
}
int main(){
cin>>n>>m;
for(int i=1,u,v,c,f;i<=m;i++)
cin>>u>>v>>c>>f,G[u].push_back({v,c,f}),G[v].push_back({u,c,f});
int l=1,r=1000;
while(l<=r){
int mid=(l+r)>>1;
dijkstra(1,mid);
if(dis[n]!=0x3f3f3f3f) l=mid+1,ans=1000000*mid/dis[n];
else r=mid-1;
}
cout<<ans;
return 0;
}
T2
考虑 dp，在松弛操作时进行转移。
当 dijkstra 发现一条新的最短路点时，直接继承即可。
否则如果发现邻接点 \(dis\) 值与当前最优值相等，加上当前点的 \(dp\) 值即可。
#include<bits/stdc++.h>
using namespace std;
const int MOD=100003,N=1000031;
int n,m,ans;
int dis[N],cnt[N];
bool vis[N];
vector<int> G[N<<1];
struct Node{
int u,w;
bool operator < (const Node &b) const{
return w>b.w;
}
};
void dijkstra(){
memset(dis,0x3f,sizeof(dis));
cnt[1]=1,dis[1]=0;
priority_queue<Node> pq; pq.push({1,0});
while(!pq.empty()){
Node now=pq.top(); pq.pop();
if(vis[now.u]) continue; vis[now.u]=1;
for(auto i:G[now.u]){
if(dis[i]>dis[now.u]+1)
dis[i]=dis[now.u]+1,
cnt[i]=cnt[now.u],
pq.push({i,dis[i]});
else if(dis[i]==dis[now.u]+1)
cnt[i]=(cnt[i]+cnt[now.u])%MOD;
}
}
}
int main(){
cin>>n>>m;
for(int i=1,u,v;i<=m;i++)
cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
dijkstra();
for(int i=1;i<=n;i++) cout<<cnt[i]%MOD<<'\n';
return 0;
}
T3
题意可转化为求免费完 \(k\) 对之后最大边权的最小值。
一眼二分。
考虑在 check 中重建图，令原边权 \(>mid\) 的边边权为 \(1\)，\(<mid\) 的边边权为 \(0\)。
然后跑一边 dijkstra 求出需要免费的点对，
若数量 \(\le k\)，则猜小，否则猜大即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1031,M=10031;
int n,m,k,ans;
int dis[N];
bool vis[N];
struct P{ int a,b,l; }p[M];
struct E{ int v,w; };
vector<E> G[M];
struct Node{
int u,w;
bool operator < (const Node &b) const{
return w>b.w;
}
};
void dijkstra(){
memset(vis,0,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
priority_queue<Node> pq; pq.push({1,0});
while(!pq.empty()){
Node now=pq.top(); pq.pop();
if(vis[now.u]) continue; vis[now.u]=1;
for(auto i:G[now.u]){
if(dis[i.v]>dis[now.u]+i.w)
dis[i.v]=dis[now.u]+i.w,
pq.push({i.v,dis[i.v]});
}
}
}
bool check(int x){
for(int i=1;i<=n;i++) G[i].clear();
for(int i=1;i<=m;i++)
G[p[i].a].push_back({p[i].b,(p[i].l>x)}),
G[p[i].b].push_back({p[i].a,(p[i].l>x)});
dijkstra();
return dis[n]<=k;
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=m;i++) cin>>p[i].a>>p[i].b>>p[i].l;
int l=0,r=1e6+1;
while(l+1<r){
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid;
}
if(r==1e6+1) cout<<-1;
else cout<<r;
return 0;
}
作业 T1
我们跑两遍 dijkstra，求得 \(1,n\) 到其他点的最短路，记为 \(x_i,y_i\)。
于是答案即为 \(\min(T,\max\{x_i+y_j+1\})\)。
直接算是 \(O(n \log n+n^2)\) 的，T 飞。
于是对于升序的 \(x_i\)，下面有两个引理：
- 引理 \(1\)：对于每个 \(x_i\)，仅需考虑其右边的 \(y_i\)。
证明：
若 \(j<i\)，则有 \(x_i+y_j \ge x_j+y_j \ge T\)，其不影响答案。
证毕
- 引理 \(2\)：对于每个 \(x_i\)，仅需考虑 \(y_{i+1}\)。
证明：
若 \(y_{i+1} \ge y_i\)，则有 \(x_i+y_{i+1} \ge x_i+y_i \ge T\)，说明考虑 \(j \ge i+1\) 的情况均对答案无影响。
否则说明 \(y_i\) 降序，则最大值一定出现在 \(y_{i+1}\)。
证毕
综上，答案即为 \(\min(T,\max\{x_i+y_{i+1}+1\})\)。
时间复杂度 \(O(n \log n + n)\)
#include<bits/stdc++.h>
using namespace std;
const int N=2000031;
int n,m,k,ans,p[N];
int dis1[N],disn[N];
bool vis[N];
vector<int> G[N<<1];
struct Node{
int u,w;
bool operator < (const Node &b) const{ return w>b.w; }
};
bool cmp(int x,int y){ return dis1[x]<dis1[y]; }
void dijkstra_1(){
memset(vis,0,sizeof(vis));
memset(dis1,0x3f,sizeof(dis1)),dis1[1]=0;
priority_queue<Node> pq; pq.push({1,0});
while(!pq.empty()){
Node now=pq.top(); pq.pop();
if(vis[now.u]) continue; vis[now.u]=1;
for(auto i:G[now.u]){
if(dis1[i]>dis1[now.u]+1)
dis1[i]=dis1[now.u]+1,
pq.push({i,dis1[i]});
}
}
}
void dijkstra_n(){
memset(vis,0,sizeof(vis));
memset(disn,0x3f,sizeof(disn)),disn[n]=0;
priority_queue<Node> pq; pq.push({n,0});
while(!pq.empty()){
Node now=pq.top(); pq.pop();
if(vis[now.u]) continue; vis[now.u]=1;
for(auto i:G[now.u]){
if(disn[i]>disn[now.u]+1)
disn[i]=disn[now.u]+1,
pq.push({i,disn[i]});
}
}
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=k;i++) cin>>p[i];
for(int i=1,u,v;i<=m;i++) cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
dijkstra_1(),dijkstra_n(),sort(p+1,p+k+1,cmp);
for(int i=1;i<k;i++) ans=max(ans,dis1[p[i]]+disn[p[i+1]]+1);
ans=min(ans,dis1[n]),cout<<ans;
return 0;
}