【BZOJ3691】游行
Description
每年春季，在某岛屿上都会举行游行活动。
在这个岛屿上有N个城市，M条连接着城市的有向道路。
你要安排英雄们的巡游。英雄从城市si出发，经过若干个城市，到城市ti结束，需要特别注意的是，每个英雄的巡游的si可以和ti相同，但是必须至少途径2个城市。
每次游行你的花费将由3部分构成：
1.每个英雄游行经过的距离之和，需要特别注意的是，假如一条边被途径了k次，那么它对答案的贡献是k*ci，ci表示这条边的边权。
2.如果一个英雄的巡游的si不等于ti，那么会额外增加C的费用。因为英雄要打的回到起点。
3.如果一个城市没有任何一个英雄途经，那么这个城市会很不高兴，需要C费用的补偿。
你有无数个的英雄。你要合理安排游行方案，使得费用最小。
由于每年，C值都是不一样的。所以你要回答Q个询问，每个询问都是，当C为当前输入数值的时候的答案。
Input
第一行正整数N，M，Q；
接下来的M行，每行ai,bi,ci，表示有一条从ai到bi，边权为ci的有向道路。保证不会有自环，但不保证没有重边。
接下来Q行，每行一个C，表示询问当每次费用为C时的最小答案。
Output
Q行，每行代表一个询问的答案。
Sample Input
1 3 2
2 3 2
3 4 2
4 5 2
4 6 2
1
5
10
Sample Output
21
32
HINT
【样例说明】
第一年的时候，C只有1。我们比较懒所以就不安排英雄出游了，需要支付6的费用。
第二年的时候，我们可以这么安排：
第一个英雄1->3->4->5，需要付2+2+2=6的费用，同时还要花5费用打的回家。再花5+5的费用来补偿2号城市和6号城市。
第三年略。
【数据范围】
对于100%的数据，2<=N<=250,1<=M<=30000,1<=Q<=10000。
1<=ci<=10000,1<=C<=10000。
题解：比较难的费用流建模题。
首先由于每次的C不同，我们建的图中是不能包含C这个东西的，但是C的代价怎么算呢？我们可以将题意理解为：选择若干条路径<a,b>（a!=b），每条路径只覆盖路径的终点，最后所有没被覆盖的点都要付出C的代价。回忆最小覆盖的方法，我们拆点建出图：
先跑floyd得到任意两点间的最短路dis(a,b)（a!=b），然后：
1.a -> b' 容量1，费用dis(a,b)
2.S -> a 容量1，费用0
3.a' -> T 容量1，费用0
那么我们跑费用流的时候，每增广一次，就用当前的 costflow+C*没被覆盖的点数 更新答案即可。
但是这样还是不能通过此题，不过我们发现，每增广一次所需要的费用是不断增大的，也就意味着存在一个时刻，使得之前每增广一次的费用都小于等于C，之后的每次增广的费用都大于C。所以我们可以记录下每次增广需要的费用，存到数组里，查询时二分一下即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
int n,m,Q,tot,S,T,cnt;
int head[1000],dis[1000],pv[1000],pe[1000],to[1000000],next[1000000],cost[1000000],flow[1000000],val[1000],inq[1000];
int s[1000],map[300][300];
queue<int> q;
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar();
return ret*f;
}
inline void add(int a,int b,int c,int d)
{
to[cnt]=b,cost[cnt]=c,flow[cnt]=d,next[cnt]=head[a],head[a]=cnt++;
to[cnt]=a,cost[cnt]=-c,flow[cnt]=0,next[cnt]=head[b],head[b]=cnt++;
}
int bfs()
{
memset(dis,0x3f,sizeof(dis));
q.push(S),dis[S]=0;
int i,u;
while(!q.empty())
{
u=q.front(),q.pop(),inq[u]=0;
for(i=head[u];i!=-1;i=next[i]) if(flow[i]&&dis[to[i]]>dis[u]+cost[i])
{
dis[to[i]]=dis[u]+cost[i],pe[to[i]]=i,pv[to[i]]=u;
if(!inq[to[i]]) inq[to[i]]=1,q.push(to[i]);
}
}
return dis[T]<0x3f3f3f3f;
}
int main()
{
n=rd(),m=rd(),Q=rd(),S=0,T=2*n+1;
memset(head,-1,sizeof(head));
int i,j,k,a,b,c,l,r,mid;
memset(map,0x3f,sizeof(map));
for(i=1;i<=n;i++) map[i][i]=0;
for(i=1;i<=m;i++) a=rd(),b=rd(),c=rd(),map[a][b]=min(map[a][b],c);
for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i!=j) add(i,j+n,map[i][j],1);
for(i=1;i<=n;i++) add(S,i,0,1),add(i+n,T,0,1);
while(bfs())
{
val[++tot]=dis[T],s[tot]=s[tot-1]+val[tot];
for(i=T;i!=S;i=pv[i]) flow[pe[i]]--,flow[pe[i]^1]++;
}
for(i=1;i<=Q;i++)
{
a=rd(),l=0,r=tot+1;
while(l<r)
{
mid=(l+r)>>1;
if(val[mid]<a) l=mid+1;
else r=mid;
}
printf("%d\n",s[l-1]+(n-l+1)*a);
}
return 0;
}