题面
http://darkbzoj.tk/problem/3691
题解
update 2020.2.12
最后的匹配中，对于任意 $X$ 部中的点集 $S subseteq X$，定义其对应的 $Y$ 部的集合为 $w(S)$。
若对于每一个 $x in S$，都有 $x' in w(S)$，则称 $S$ 是一个英雄游行的路径。
看着那么多询问，肯定不可能建图重新跑，就知道其中必有高论。
首先可以重复经过，所以$Floyed$求传递闭包。
你可以想象在二分图的$X$部，有$n$个嗷嗷待哺的$+c$，用一个匹配能解决掉一个，但是有的时候解决掉匹配的反而比$c$大，那就不划算了。
所以记录最小费用最大流过程中的$dis[T]$（一定递增），查询的时候直接在上面二分查就可以了。
#include<map> #include<stack> #include<queue> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 1000 #define S 0 #define T (2*n+1) #define LL long long #define ri register int #define INF 1000000007 using namespace std; int n,m,k,cc,q; int dis[N][N]; LL tot[N]; int cai[N],wei[N]; struct graph { vector<int> to,w,c; vector<int> ed[N]; LL dis[N]; int cur[N]; bool vis[N]; void add_edge(int a,int b,int aw,int ac) { to.push_back(b); w.push_back(aw); c.push_back(ac); ed[a].push_back(to.size()-1); to.push_back(a); w.push_back(0); c.push_back(-ac); ed[b].push_back(to.size()-1); } bool spfa() { memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); queue<int> q; dis[S]=0;q.push(S);vis[S]=1; while (!q.empty()) { int x=q.front(); q.pop(); for (ri i=0;i<ed[x].size();i++) { int e=ed[x][i]; if (dis[to[e]]>dis[x]+c[e] && w[e]) { dis[to[e]]=dis[x]+c[e]; if (!vis[to[e]]) vis[to[e]]=1,q.push(to[e]); } } vis[x]=0; } return dis[T]<INF; } int dfs(int x,int lim) { if (x==T || !lim) return lim; LL sum=0; vis[x]=1; for (ri &i=cur[x];i<ed[x].size();i++) { int e=ed[x][i]; if (dis[x]+c[e]==dis[to[e]] && w[e] && !vis[to[e]]) { int f=dfs(to[e],min(lim,w[e])); w[e]-=f; w[1^e]+=f; lim-=f; sum+=f; if (!lim) return sum; } } return sum; } void zkw() { LL ret=0; cc=0; while (spfa()) { memset(vis,0,sizeof(vis)); memset(cur,0,sizeof(cur)); int f=dfs(S,INF); ret+=f*dis[T]; ++cc; cai[cc]=dis[T]; tot[cc]=ret; wei[cc]=wei[cc-1]+f; } } } G; int main() { int a,b,l; scanf("%d %d %d",&n,&m,&k); memset(dis,0x3f,sizeof(dis)); for (ri i=1;i<=n;i++) dis[i][i]=0; for (ri i=1;i<=m;i++) { scanf("%d %d %d",&a,&b,&l); dis[a][b]=min(dis[a][b],l); } for (ri kk=1;kk<=n;kk++) for (ri i=1;i<=n;i++) for (ri j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][kk]+dis[kk][j]); for (ri i=1;i<=n;i++) for (ri j=1;j<=n;j++) if (i!=j) G.add_edge(i,n+j,1,dis[i][j]); for (ri i=1;i<=n;i++) G.add_edge(S,i,1,0); for (ri i=n+1;i<=2*n;i++) G.add_edge(i,T,1,0); wei[0]=0; G.zkw(); for (ri i=1;i<=k;i++) { scanf("%d",&q); int x=lower_bound(cai+1,cai+cc+1,q)-cai; x--; printf("%lld ",(n-wei[x])*1LL*q+tot[x]); } }