BZOJ3691 游行 <二分+费用流>

Problem

游行

Time Limit:
Memory Limit:

Description

每年春季，在某岛屿上都会举行游行活动。
在这个岛屿上有个城市，条连接着城市的有向道路。
你要安排英雄们的巡游。英雄从城市出发，经过若干个城市，到城市结束，需要特别注意的是，每个英雄的巡游的可以和相同，但是必须至少途径2个城市。
每次游行你的花费将由部分构成：

每个英雄游行经过的距离之和，需要特别注意的是，假如一条边被途径了次，那么它对答案的贡献是，表示这条边的边权。
如果一个英雄的巡游的不等于，那么会额外增加的费用。因为英雄要打的回到起点。
如果一个城市没有任何一个英雄途经，那么这个城市会很不高兴，需要费用的补偿。

你有无数个的英雄。你要合理安排游行方案，使得费用最小。
由于每年，值都是不一样的。所以你要回答个询问，每个询问都是，当为当前输入数值的时候的答案。

Input

第一行正整数。
接下来的行，每行，表示有一条从到，边权为的有向道路。保证不会有自环，但不保证没有重边。
接下来行，每行一个，表示询问当每次费用为时的最小答案。

Output

行，每行代表一个询问的答案。

Sample Input

Sample Output

1
2
3

6
21
32

HINT

样例说明
第一年的时候，只有。我们比较懒所以就不安排英雄出游了，需要支付的费用。
第二年的时候，我们可以这么安排：
一个英雄，需要付的费用，同时还要花5费用打的回家。再花的费用来补偿号城市和号城市。
第三年略。
数据范围
对于的数据，, , , , 。

标签：二分 费用流

Solution

比较难想但很奇妙的费用流建模。
题目可以转化为：选择若干条带权路径，选择指覆盖终点，所有没被覆盖的点都要付出的代价，每次给定求最小代价。
首先用算出多源最短路把每个点拆成入点和出点，建图：
容量费用
容量费用
容量费用
每次增广均会有前面未覆盖的点被覆盖，即用增广一次的代价来代替。若增广前代价为，则增广后为。记录每次增广增加的费用，可知这个费用是单增的，推得当时，可增广使答案变小，而当时，继续增广会使答案变大。因此对每个询问二分出的分界点计算答案即可。

Code

#include <bits/stdc++.h>
#define MAX_N 500
#define MAX_M 100000
#define mid ((l+r)>>1)
#define INF 0x3f3f3f3f
using namespace std;
int n, m, q, x, s, t, cnt, pr[MAX_N+5], cr[MAX_N+5], f[MAX_N+5], g[MAX_N+5];
struct node {int v, c, w, nxt;} E[MAX_M+5];	int G[MAX_N+5][MAX_N+5], tot, cost;
void init() {s = 0, t = n*2+1, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c, int w) {E[cnt] = (node){v, c, w, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c, int w) {insert(u, v, c, w), insert(v, u, 0, -w);}
bool SPFA() {
    queue <int> que;	bool inq[MAX_N+5];	int d[MAX_N+5], cr[MAX_N+5];
    memset(inq, false, sizeof inq), memset(d, INF, sizeof d);
    d[s] = 0, que.push(s), inq[s] = true, memset(cr, -1, sizeof cr);
    while (!que.empty()) {
        int u = que.front();	que.pop(), inq[u] = false;
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c, w = E[i].w;
            if (c && d[u]+w < d[v]) {
                d[v] = d[u]+w, cr[v] = i;
                if (!inq[v]) que.push(v), inq[v] = true;
            }
        }
    }
    if (d[t] == INF) return false;	int flow = INF;
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) flow = min(flow, E[i].c);
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) E[i].c -= flow, E[i^1].c += flow;
    cost = d[t];	return true;
}
int bi_search(int l, int r) {while (l <= r) f[mid] < x ? l = mid+1 : r = mid-1;	return g[l-1]+(n-l+1)*x;}
int main() {
    scanf("%d%d%d", &n, &m, &q), init();	memset(G, INF, sizeof G);
    for (int i = 1; i <= n; i++) addedge(s, i, 1, 0), addedge(i+n, t, 1, 0), G[i][i] = 0;
    for (int i = 0, u, v, c; i < m; i++) scanf("%d%d%d", &u, &v, &c), G[u][v] = min(G[u][v], c);
    for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) G[i][j] = min(G[i][j], G[i][k]+G[k][j]);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
        if (G[i][j]^INF && (i^j)) addedge(i, j+n, 1, G[i][j]);
    while (SPFA()) f[++tot] = cost, g[tot] = f[tot]+g[tot-1];
    while (q--) scanf("%d", &x), printf("%d\n", bi_search(0, tot));
    return 0;
}