本题解的代码可以过(Open Judge原题的数据)
题目描述(略,下方有链接,请自行点击)
AcWing地址: https://www.acwing.com/problem/content/371/
Virtual Judge地址: https://cn.vjudge.net/problem/OpenJ_POJ-1044
$\text{算法:有向无环图必经边的简单判定 + 拓扑排序 + DP}$
顺便说一句,如果是无向图的话,直接上圆方树就可以了,例题洛谷P4606 [SDOI2018]战略游戏, P4320 道路相遇
$\text{吐槽一句,为啥lyd自己在冬令营上都讲过的题,成为全书极少的没有标程的题目,赶紧过来试水}$
突然发现全书的神题是P332 How many of them ? 2019.9.3 update
思路和lyd书上的完全一致,只是提供一个代码实现的范例
另外书上所说的用动态规划的方法求出$ds[i]$和$dt[i]$数组感觉有误,实际上那不是动规吧, 用类似于双指针的方法扫一遍即可
大家可以在演草纸上易证在最优解中上车下车的两个端点中一定有一个可以放在原图中的点上,因此我们才能用$ds[i] + dt[i]$更新答案
代码只有170行(打起来蛮舒服的),阅读愉快
时间复杂度$\Theta(T\times n)$, T代表数据组数
C++ 代码
//ID: LRL52 Date: 2019.8.26
//这就是传说中1%的没有数据没有标程的题目?
//lyd判定有向无环图的必经点和必经边的方法很妙啊
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define ee(i, a) for(int i = head[a]; i; i = e[i].nxt)
//#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1e5 + 55, M = 2e5 + 55; char ss[1 << 21], *A = ss, *B = ss, cc;
inline char gc(){return A == B && (B = (A = ss) + fread(ss, 1, 1 << 21, stdin), A == B) ? EOF : *A++;}
template<class T>inline void rd(T &x){
int f = 1; x = 0, cc = gc(); while(cc < '0' || cc > '9'){if(cc == '-') f = -1; cc = gc();}
while(cc >= '0' && cc <= '9'){x = (x << 3) + (x << 1) + (cc ^ 48); cc = gc();} x *= f;
}
typedef long long ll;
const int P[2] = {1000000007, 1000000009};
int ct, n, m, St, Ed, K, cnt, _ct;
int head[N], fs[N][2], ft[N][2], in[N], out[N], pre[N], path[N], _head[N];
int Efrom[N], Eto[N];
ll sum[N], ds[N], dt[N], dis[N];
struct edge{
int v, nxt, w;
}e[M], _e[M];
queue<int> q;
inline void adde(int from, int to, int w){
e[++ct].v = to;
e[ct].w = w;
e[ct].nxt = head[from];
head[from] = ct;
}
inline void _adde(int from, int to, int w){
_e[++_ct].v = to;
_e[_ct].w = w;
_e[_ct].nxt = _head[from];
_head[from] = _ct;
}
void topsort(){
fs[St][0] = fs[St][1] = 1;
dis[St] = 0;
rep(i, 1, n) if(!in[i]) q.push(i);
while(!q.empty()){
int now = q.front(); q.pop();
ee(i, now){
int v = e[i].v;
fs[v][0] = (fs[v][0] + fs[now][0]) % P[0];
fs[v][1] = (fs[v][1] + fs[now][1]) % P[1];
if(dis[now] + e[i].w < dis[v])
dis[v] = dis[now] + e[i].w, pre[v] = now;
if(--in[v] == 0) q.push(v);
}
}
}
void topsort2(){
ft[Ed][0] = ft[Ed][1] = 1;
rep(i, 1, n) if(!out[i]) q.push(i);
while(!q.empty()){
int now = q.front(); q.pop();
for(int i = _head[now]; i; i = _e[i].nxt){
int v = _e[i].v;
ft[v][0] = (ft[v][0] + ft[now][0]) % P[0];
ft[v][1] = (ft[v][1] + ft[now][1]) % P[1];
if(--out[v] == 0) q.push(v);
}
}
}
void getpath(int x){
if(pre[x]) getpath(pre[x]);
path[++cnt] = x;
}
void work_the_same(){
sum[cnt] = 0;
for(int i = cnt; i > 1; --i){
int w = 0, now = path[i];
ee(j, path[i - 1]){
int v = e[j].v;
if(v == now){
w = e[j].w;
break;
}
}
sum[i - 1] = sum[i];
if(Efrom[path[i - 1]] && Eto[now])
sum[i - 1] += w;
}
int p = cnt;
dt[cnt + 1] = 0;
for(int i = cnt; i >= 1; --i){
while(dis[path[p]] - dis[path[i]] > K) --p;
dt[i] = dt[i + 1];
ll nowans = sum[i] - sum[p];
if(Efrom[path[p]])
nowans += K - (dis[path[p]] - dis[path[i]]);
dt[i] = max(dt[i], nowans);
}
}
int main(){
freopen("PKU_ACM.in", "r", stdin);
//freopen("PKU_ACM.out", "w", stdout);
int T; rd(T); int x, y, z;
while(T--){
rd(n), rd(m), rd(St), rd(Ed), rd(K); ++St, ++Ed;
ct = _ct = 0;
memset(head, 0, sizeof(head));
memset(_head, 0, sizeof(_head));
memset(in, 0, sizeof(in));
memset(out, 0, sizeof(out));
rep(i, 1, m){
rd(x), rd(y), rd(z);
++x, ++y;
adde(x, y, z);
_adde(y, x, z);
++in[y], ++out[x];
}
memset(dis, 0x3f, sizeof(dis));
memset(fs, 0, sizeof(fs));
memset(pre, 0, sizeof(pre));
topsort();
if(dis[Ed] == dis[0]){
puts("-1");
continue;
}
memset(ft, 0, sizeof(ft));
topsort2();
cnt = 0;
getpath(Ed);
sum[1] = 0;
memset(Efrom, 0, sizeof(Efrom));
memset(Eto, 0, sizeof(Eto));
rep(i, 1, cnt - 1){
int y = 0, w = 0, now = path[i];
ee(j, now){
int v = e[j].v;
if(v == path[i + 1]){
y = v, w = e[j].w;
break;
}
}
sum[i + 1] = sum[i];
if(1LL * fs[now][0] * ft[y][0] % P[0] == 1LL * fs[Ed][0] &&
1LL * fs[now][1] * ft[y][1] % P[1] == 1LL * fs[Ed][1]){
Efrom[now] = 1, Eto[y] = 1;
sum[i + 1] += w;
}
}
int p = 1;
ds[0] = 0;
rep(i, 1, cnt){
while(dis[path[i]] - dis[path[p]] > K) ++p;
ds[i] = ds[i - 1];
ll nowans = sum[i] - sum[p];
if(Eto[path[p]])
nowans += K - (dis[path[i]] - dis[path[p]]);
ds[i] = max(ds[i], nowans);
}
work_the_same();
ll ans = 1LL << 62;
rep(i, 1, cnt)
ans = min(ans, sum[1] - (ds[i] + dt[i]));
printf("%lld\n", ans);
}
return 0;
}
不好意思,请问以下这组数据您的代码是否无法处理?
正确答案按题意应该是0,您的代码输出4
1
6 7 0 5 10
0 1 3
0 1 5
1 2 6
2 3 8
3 4 6
4 5 3
4 5 5
或者这组数据:
1
2 1 0 1 1
0 1 2