PS:本题解有误,如果在一条路上即上车又下车是解决不了的
简单难度谁顶得住啊
两遍bfs,按拓扑序找必经边
先建正图,从S出发,cnt1[i]表示从S出发到i的路径数
再建反图,从T出发,类似的求出cnt2
对于边 i = (u,v,w);
如果cnt1[u] * cnt2[v] == cnt1[T] 则说明 i 是必经边
再找出最短路,在最短路上进行dp
找最短路过程可以和bfs一起进行
单向边所以要走正图找最短路
先走反图再走正图
用pre记入边即可
因为要建反图,肯定是要把边都存下来的
dp找从S出发和从T出发只乘一次车最多少走的桥长
ds[i]代表从S出发到i车走过桥的长度
i只用枚举整点,因为如果不在整点一定可以移到整点让答案不会更差
车肯定是跑的越多越好
所以k记录最早从哪上车,直接用k转移即可
dt从T出发,与ds类似
最后枚举ds,dt的分割点,求出两次车最最多覆盖的桥长即可
还有一个证明,就是随机找最短路不影响结果:
首先,因为桥在所有路径上,所以桥一定在最短路上
把两个桥中间的部分单独来看,只关心长度而不关心具体路径
即证
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1e5+5,M = 2*N,inf = 0x3f3f3f3f,mod = 1e9 + 7;
int tot,S,T,n,m,q,idx = 1,ver[M],wet[M],nxt[M],head[N],dis[N],indu[N],edu[M],edv[M],edw[M],pre[N];
queue<int> q1;
bool bridge[M];
LL dt[N],ds[N],cnt1[N],cnt2[N],sum_b[N],sum[N];
void add(int u,int v,int w)
{
nxt[++idx] = head[u];
ver[idx] = v;
wet[idx] = w;
head[u] = idx;
}
void bfs(int st,LL a[])
{
memset(dis,inf,sizeof dis);
a[st] = 1;
q1.push(st);
dis[st] = 0;
while(q1.size())
{
int u = q1.front();q1.pop();
for(int i = head[u]; i ;i = nxt[i])
{
int v = ver[i];
indu[v] --;
if(!indu[v])q1.push(v);
a[v] = (a[u] + a[v]) % mod;
if(dis[v] > dis[u] + wet[i])
dis[v] = dis[u] + wet[i],pre[v] = i - 1;
}
}
}
void init()
{
memset(head,0,sizeof head);
memset(bridge,0,sizeof bridge);
memset(indu,0,sizeof indu);
memset(pre,0,sizeof pre);
memset(ds,0,sizeof ds);
memset(dt,0,sizeof dt);
memset(sum,0,sizeof sum);
memset(sum_b,0,sizeof sum_b);
idx = 1;
tot = 0;
}
void get_path(int x)
{
if(x != S)get_path(edu[pre[x]]);
++tot;
sum_b[tot] += sum_b[tot-1] + bridge[pre[x]] * edw[pre[x]];
sum[tot] += sum[tot-1] + edw[pre[x]];
}
void dp()
{
int k = 1;
for(int i = 2;i <= tot;i ++)
{
while( sum[i] - sum[k] > q )k++;
ds[i] = max(ds[i-1],sum_b[i] - sum_b[k] + (sum_b[k] - sum_b[k-1] > 0 ? q - (sum[i] - sum[k]) : 0 ) );
}
k = tot;
for(int i = tot - 1;i >= 1;i --)
{
while( sum[k] - sum[i] > q )k--;
dt[i] = max(dt[i+1],sum_b[k] - sum_b[i] + (sum_b[k+1] - sum_b[k] > 0 ? q - (sum[k] - sum[i]) : 0 ) );
}
}
int main()
{
int L;
cin >> L;
while(L --)
{
init();
scanf("%d%d%d%d%d",&n,&m,&S,&T,&q);
S++,T++;
int xi,yi,zi;
for(int i = 1;i <= m;i ++)
scanf("%d%d%d",&xi,&yi,&zi),add(++yi,++xi,zi),indu[xi]++,edu[i] = xi,edv[i] = yi,edw[i] = zi;
memset(cnt2,0,sizeof cnt2);
bfs(T,cnt2);
init();
for(int i = 1;i <= m;i ++)
add(edu[i],edv[i],edw[i]),indu[edv[i]]++;
memset(cnt1,0,sizeof cnt1);
bfs(S,cnt1);
for(int i = 1;i <= m;i ++)
bridge[i] = cnt1[edu[i]] * cnt2[edv[i]] % mod == cnt1[T] % mod;
get_path(T);
dp();
LL ans = 0;
for(int i = 1;i <= n;i ++)
ans = max(ds[i]+dt[i],ans);
cout << sum_b[tot] - ans << endl;
}
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
题解写的不对吧,代码过不了