NC51365. PKU ACM Team's Excursions
描述
给定一张 N 个点 M 条边的有向无环图，点的编号从 0 到 N - 1，每条边都有一个长度。
给定一个起点 S 和一个终点 T。
若从 S 到 T 的每条路径都经过某条边，则称这条边是有向图的必经边或桥。
北大 ACM 队要从 S 点到 T 点。
他们在路上可以搭乘两次车。
每次可以从任意位置（甚至是一条边上的任意位置）上车，从任意位置下车，但连续乘坐的长度不能超过 q 米。
除去这两次乘车外，剩下的路段步行。
定义从 S 到 T 的路径的危险程度等于步行经过的桥上路段的长度之和。
求从 S 到 T 的最小危险程度是多少。
输入描述
第一行包含整数 L，表示共有 L 组测试数据。
每组测试数据，第一行包含五个整数 N,M,S,T,q 。
接下来 M 行，每行包含三个整数u,v,w，表示点 u 到点 v 存在一条边，长度为 w。
输出描述
每组数据输出一个结果，每个结果占一行。
若没有从 S 到 T 的路径，则输出 -1。
示例1
输入:
1 8 9 0 7 7 0 4 1 0 1 10 1 2 9 4 2 2 2 5 8 4 3 3 5 6 6 5 6 7 6 7 5
输出:
1
C(clang 3.9) 解法, 执行用时: 532ms, 内存消耗: 11640K, 提交时间: 2020-07-23 00:36:03
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#define V 100000
#define p 1000000021
typedef struct{
int head, indeg,dp;
}Vertex;
typedef struct {
int to,next, w,isbridge;
}Edge;
const Vertex NEUTRAL_VERTEX = {-1,0,0};
const Edge NEUTRAL_EDGE = {0,-1,0, 1};
int eid,eid2;
int n,m,s,t,q;
Vertex v[V], v2[V];
Edge e[2*V], e2[2*V];
int max(int a,int b) {
return a > b ? a : b;
}
void init(int n,int m) {
eid = eid2 = 0;
for(int i=0;i<n;i++) v[i] = v2[i] = NEUTRAL_VERTEX;
}
void add(int x,int y,int w) {
e[eid] = (Edge){ y, v[x].head, w, 1 };
v[x].head = eid++;
v[y].indeg++;
}
void add2(int x,int y,int w) {
e2[eid2] = (Edge){ y, v2[x].head, w, 1 };
v2[x].head = eid2++;
v2[y].indeg++;
}
int Q[V],Qsz, indeg[V];
void cal_fs(int s,int n, const Vertex *v, Edge *e, int M,int *fs) {
for(int i=0;i<n;i++) fs[i] = 0;
fs[s] = 1;
Qsz = 0;
for(int i=0;i<n;i++) {
indeg[i] = v[i].indeg;
if(indeg[i]==0) Q[Qsz++] = i;
}
int x,y;
for(int qi=0;qi<Qsz;qi++) {
x = Q[qi];
for(int i = v[x].head; ~i; i = e[i].next ) {
y = e[i].to;
fs[y] = ( fs[y] + fs[x] ) % M;
if(--indeg[y]==0) Q[Qsz++] = y;
}
}
}
int dist[V],prev[V],pree[V],path[V], psz;
void cal_ds(int s, int t ,Vertex *v, const Edge *e) {
memset(dist,0x3f3f3f3f,sizeof(dist));
dist[s] = 0;
Qsz = 0;
for(int i=0;i<n;i++) if(v[i].indeg==0) Q[Qsz++] = i;
for(int qi = 0; qi<Qsz;qi++) {
int x = Q[qi];
for(int i = v[x].head; ~i; i = e[i].next) {
int y = e[i].to;
if(dist[x] + e[i].w < dist[y]) {
dist[y] = dist[x] + e[i].w;
pree[y] = i;
prev[y] = x;
}
if(--v[y].indeg==0) Q[Qsz++] = y;
}
}
psz = 0;
int z = t;
while(z!=s) {
path[psz++] = pree[z];
z = prev[z];
}
int temp;
for(int i=0;i<psz/2;i++) {
temp = path[i];
path[i] = path[psz-1-i];
path[psz-1-i] = temp;
}
int j = 0, len = 0, B = 0, best = 0;
for(int k = 0;k<psz;k++) {
int i = path[k];
int to = e[i].to;
len += e[i].w;
if(e[i].isbridge) B += e[i].w;
while(len>q) {
len -= e[path[j]].w;
if(e[path[j]].isbridge) B -= e[path[j]].w;
j++;
}
v[to].dp = B;
if(j>0 && e[path[j-1]].isbridge) v[to].dp += q-len;
v[to].dp = max(v[to].dp, best);
best = max(best,v[to].dp);
//printf("best = %d, i = %d, e[i].w = %d, to = %d, v[to].dp = %d\n",best, i, e[i].w, to, v[to].dp);
}
}
int fs[V],ft[V];
int main() {
int tt; scanf("%d",&tt);
while(tt--) {
scanf("%d%d%d%d%d",&n,&m,&s,&t,&q);
init(n,m);
for(int i=0;i<m;i++) {
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
if(u==v) continue;
add(u,v,w);
add2(v,u,w);
}
cal_fs(s,n,v,e,p,fs);
cal_fs(t,n,v2,e2,p,ft);
for(int x = 0; x < n; x++) {
for(int i = v[x].head; ~i; i = e[i].next) {
int y = e[i].to;
if( 1ll * fs[x] * ft[y] % p != fs[t]) e[i].isbridge = 0;
}
for(int i=v2[x].head; ~i; i=e2[i].next) {
int y = e2[i].to;
if(1ll*ft[x]*fs[y]%p != ft[s]) e2[i].isbridge = 0;
}
}
cal_ds(s,t,v,e);
cal_ds(t,s,v2,e2);
int ans = 0, temp = 0;
for(int i=0;i<m;i++) {
if(e[i].isbridge) {
ans += e[i].w;
}
}
for(int i=0;i<n;i++) {
temp = max(temp, v[i].dp + v2[i].dp);
}
printf("%d\n",ans-temp);
}
return 0;
}
C++14(g++5.4) 解法, 执行用时: 411ms, 内存消耗: 26904K, 提交时间: 2020-09-23 23:11:50
#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;
}
}
C++ 解法, 执行用时: 483ms, 内存消耗: 11544K, 提交时间: 2022-04-10 19:38:40
#include <bits/stdc++.h>
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;
}
}