傻波学校测评机，模拟赛直接吞我 25 分。

题意描述

题目链接

给定一个 $n$ 个点，$m$ 条边的有向图（不保证没有重边）,经过第 $i$ 条边花费 $w_i$ 的费用，定义一次操作的费用为：

选择一个起点 $s_i$，终点 $t_i$ 以及一条 $s_i$ 到 $t_i$ 的路径，访问路径上经过的所有点。这部分的代价为路径的费用。但是如果 $s_i \neq t_i$，则需要额外的代价 $C$。需要注意的是，虽然允许选择的 $s_i=t_i$，但选择的路径必须经过至少一条边。

可以进行任意次(也可以不进行)上面的操作。在全部操作结束后，对于所有没有访问过的点，可以用 $C$ 的费用单独访问一个点。这部分的费用即为乘上没有访问过的点数。

现在有 $Q$ 个询问，给出 $C$，求访问所有点的最小费用。

思路

注意如果一条路径是环则该条路径不会计算 $C$ 的费用。

因为多条路径可以重复经过一个点，这比较难处理，所以我们稍微转化一下：

定义路径上的一个点是关键点当且仅当这个点没有被之前的路径覆盖。

可以发现，最优解中每个点至少包含一个关键点，且以关键点开头以关键点结尾。

考虑只保留路径上的关键点，在相邻两个关键点 $(i,j)$ 之间，最小费用显然是 $dis_{i\to j}$。

此时考虑一个新的图，其中 $i\to j$ 的费用为原图的 $dis_{i\to j}$。

此时路径满足如下限制：

  1. 每条路径是一条链或者一个环。

  2. 每个点只被一条路径覆盖。

考虑在这个图上选路径，每条路径对应原来这个路径经过的所有关键点，可以发现这样一定存在一种方式等于最优解。

再考虑费用中关于 $C$ 的部分，一个没有被覆盖的点和一条链都会让费用 $+C$，此时可以发现，这部分费用即为$(n-路径总边数)\times C$。

可以发现，在不固定的时候，只需要对于每一个 $k$，求出选条满足条件的边的最小费用 $w_k$，答案即为 $\min_{i=0}^{k}w_i+(n-i)C$。

（上面几段是教练给的题解部分，只做了细小修改）

现在考虑求 $w_i$，发现新建的图上的路径所有点只能经过一次，所以很容易联想到网络流。

考虑拆点，将点 $i$ 拆为 $in_i,out_i$。

$\forall i$，连边 $(S\to in_i),(out_i\to T)$，流量为 $1$，费用为 $0$。

$\forall (i\to j)$，连边 $(in_i\to out_j)$，流量为 $1$，费用为 $dis_{i\to j}$。

这样跑费用流就是在DAG情况下最少路径覆盖全部点的最小代价，也是在本题中用 $k$ 条边覆盖 $n$ 个点的最小费用。

考虑正确性：

此时图为一个二分图，左部点为 $in$，右部点为 $out$，此时就是在跑二分图带权最大匹配。

一条边 $(in_i\to out_j)$ 是匹配边就相当于边 $(i\to j)$ 在路径上。

这只是解决了求边数上界的问题，但是还是没有求出 $w$。

但是我们发现，如果我们每次增广只增加一条匹配边的话，就代表多连了一条边。

所以我们每次都只增广一条匹配边，并且在匹配后记录一下当前最小费用即可。

代码

#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
struct sss
{
    int q,w,e,r,nxt;
}a[1000005];
int cnt,head[1000005],d[1000005],n,now[1000005],m,N,S,T,vis[1000005],mx,dis[1005][1005],Q;
queue<int>q;
void adde(int q,int w,int e,int r)
{
    a[++cnt].q=q;
    a[cnt].w=w;
    a[cnt].e=e;
    a[cnt].r=r;
    a[cnt].nxt=head[q];
    head[q]=cnt;
    a[++cnt].q=w;
    a[cnt].w=q;
    a[cnt].e=0;
    a[cnt].r=-r;
    a[cnt].nxt=head[w];
    head[w]=cnt;
}
bool spfa()
{
    memset(d,0x3f,sizeof(d));
    while(q.size())q.pop();
    q.push(S);
    d[S]=0;
    vis[S]=1;
    now[S]=head[S];
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=a[i].nxt)
        {
            if(a[i].e&&d[a[i].w]>d[x]+a[i].r)
            {
                now[a[i].w]=head[a[i].w];
                d[a[i].w]=d[x]+a[i].r;
                if(!vis[a[i].w])q.push(a[i].w),vis[a[i].w]=1;
            }
        }
    }
    return d[T]!=0x3f3f3f3f;
}
int dinic(int x,int flow)
{
    if(x==T)return flow;
    vis[x]=1;
    int rest=flow;
    for(int i=now[x];i&&rest;i=a[i].nxt)
    {
        now[x]=i;
        if(!vis[a[i].w]&&a[i].e&&d[a[i].w]==d[x]+a[i].r)
        {
            int k=dinic(a[i].w,min(rest,a[i].e));
            if(!k)d[a[i].w]=0;
            mx+=k*a[i].r;
            a[i].e-=k;
            a[i%2?i+1:i-1].e+=k;
            rest-=k;
        }
    }
    vis[x]=0;
    return flow-rest;
}//网络流部分，直接上板子即可
int w[100005];
signed main()
{
    memset(dis,0x3f,sizeof(dis));
    scanf("%d%d%d",&n,&m,&Q);
    S=2*n+1;
    T=2*n+2;
    for(int i=1;i<=m;i++)
    {
        int q,w,e;
        scanf("%d%d%d",&q,&w,&e);
        dis[q][w]=min(e,dis[q][w]);
    }
    for(int i=1;i<=n;i++)dis[i][i]=0;
    for(int k=1;k<=n;k++) 
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
        }
    }//Floyd
    for(int i=1;i<=n;i++)adde(S,i,1,0),adde(i+n,T,1,0);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)if(i!=j)adde(i,j+n,1,dis[i][j]);
    }//建模
    int flow,ans=0;
    while(spfa())while((flow=dinic(S,1)))ans+=flow,w[ans]=mx;//记录w
    //每次只增广一条边，就体现在dinic源点初始流量为1上
    //但直接用EK好像也没有什么问题（
    while(Q--)
    {
        int c;
        scanf("%d",&c);
        long long an=1e18;
        for(int i=0;i<=ans;i++)an=min(an,(long long)w[i]+(long long)(n-i)*c);
        printf("%lld\n",an);
    }
}