CodeChef PARADE

题目大意

给定一张$n$个点$m$条边的有向带边权图。
现在要选择一些至少经过一条边的路径(不一定是简单路径),花费的代价如下:
$\bullet$ 经过的所有边的长度之和,一条边被一条或多条路径经过多次,费用需要计算多次。
$\bullet$ 如果一条路径起点和终点不一样,则多花费$C$的代价。
$\bullet$ 如果一个点没有被任何路径经过,则多花费$C$的代价。
$q$次询问,每次给出$C$,最小化总花费。

$2\leq n\leq 250,1\leq m\leq3\times10^4,1\leq q\leq 10^4$
保证给定的图没有自环,但是可能会有重边。


题目分析

多条路径可能会出现重复,这个不利于我们的计算。考虑人为地将经过的每一个点划分到某一条路径上,这样我们每一条路径都有若干“必须经过的点”。可以发现,在这些点之间肯定是走最短路最优。
因此考虑对原图求一次多源最短路,然后建一个新的图,两点$(x,y)$之间连的有向边权值是原图$x$到$y$的最短路。
根据上面所说,在最优情况下,新图中若干条不相交的路径,就可以对应于原图中的若干条合法路径。
既然现在我们要求不相交了,问题就好做了很多。考虑拆点网络流。$S\rightarrow x$、$x’\rightarrow T$连容量为$1$费用为$0$的边,$x\rightarrow y’$连容量为$1$费用为$dis_{x,y}$的边,跑最小费用流。
现在考虑加上$C$这个代价,可以发现,当增广的流量为$flow$的时候,我们的代价就是$(n-flow)C$:如果选择的某一条路径没有成环,那么经过的边数就是$flow$,点数就是$flow+1$,但是还要付出不成环的代价,也就是$(n-flow)C$;如果成环,那么经过的边数和点数都是$flow$,代价依然是$(n-flow)C$。
那么对于单次询问$C$,我们可以直接每次单路增广,取最后一次增广费用$<C$的总费用作为答案。
不过现在是多次询问,我们不妨预处理每次单路增广的费用增量。由最小费用流的性质,这个值一定是单调不下降的,因此回答询问直接二分找到合适的位置就可以回答询问了。
时间复杂度$O\left(\mathrm{Maxflow}(n,n^2)+q\log n+n^3\right)$。


代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstdio>
#include <cctype>
#include <queue>

using namespace std;

inline int read()
{
int x=0,f=1;
char ch=getchar();
while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}

int buf[30];

inline void write(int x)
{
if (x<0) putchar('-'),x=-x;
for (;x;x/=10) buf[++buf[0]]=x%10;
if (!buf[0]) buf[++buf[0]]=0;
for (;buf[0];putchar('0'+buf[buf[0]--]));
}

const int INF=INT_MAX>>1;
const int N=255;

int sum[N],cst[N];
int dis[N][N];
int n,m,q,flow;

namespace network
{
const int V=N<<1;
const int E=N*N+(N<<1)<<1;

int tov[E],nxt[E],f[E],v[E],c[E],r[E];
int last[V],dist[V],fp[V],fe[V];
bool exist[V];
int s,t,tot,cost;
queue<int> q;

inline void insert(int x,int y,int full,int cst,int rev){tov[++tot]=y,f[tot]=full,c[tot]=cst,r[tot]=tot+rev,nxt[tot]=last[x],last[x]=tot;}
inline void addedge(int x,int y,int full,int cst){insert(x,y,full,cst,1),insert(y,x,0,-cst,-1);}

inline bool spfa()
{
for (int x=s;x<=t;++x) dist[x]=INF;
dist[s]=0,q.push(s),exist[s]=1;
for (int x;!q.empty();)
{
x=q.front(),q.pop(),exist[x]=0;
for (int i=last[x],y;i;i=nxt[i])
if (dist[y=tov[i]]>dist[x]+c[i]&&f[i]-v[i])
{
dist[y]=dist[x]+c[i],fp[y]=x,fe[y]=i;
if (!exist[y]) q.push(y),exist[y]=1;
}
}
if (dist[t]==INF) return 0;
for (int x=t,i;x!=s;x=fp[x]) cost+=c[i=fe[x]],++v[i],--v[r[i]];
return 1;
}

void calc()
{
cst[0]=0;
for (flow=1;flow<=n;++flow)
{
cost=0;
if (spfa()) sum[flow]=sum[flow-1]+(cst[flow]=cost);
else break;
}
--flow;
}

void build()
{
s=0,t=n<<1|1;
for (int x=1;x<=n;++x) addedge(s,(x<<1)-1,1,0),addedge(x<<1,t,1,0);
for (int x=1;x<=n;++x)
for (int y=1;y<=n;++y)
if (x!=y) addedge((x<<1)-1,y<<1,1,dis[x][y]);
}
};

void floyd()
{
for (int k=1;k<=n;++k)
for (int i=1;i<=n;++i)
if (i!=k)
for (int j=1;j<=n;++j)
if (i!=j&&j!=k)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}

int main()
{
freopen("parade.in","r",stdin),freopen("parade.out","w",stdout);
n=read(),m=read(),q=read();
for (int x=1;x<=n;++x)
{
for (int y=1;y<=n;++y) dis[x][y]=INF;
dis[x][x]=0;
}
for (int i=1,x,y,z;i<=m;++i) x=read(),y=read(),z=read(),dis[x][y]=min(dis[x][y],z);
for (floyd(),network::build(),network::calc();q--;)
{
int c=read(),ret=0,l=0,r=flow;
for (int mid;l<=r;)
{
mid=l+r>>1;
if (cst[mid]<c) l=(ret=mid)+1;
else r=mid-1;
}
write(sum[ret]+(n-ret)*c),putchar('\n');
}
fclose(stdin),fclose(stdout);
return 0;
}