BZOJ3691 游行 <二分+费用流>

Posted on Symbols count in article: 1.3k Reading time ≈ 5 mins.

Problem

游行

Time Limit: 10Sec10 Sec
Memory Limit: 512MB512 MB

Description

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

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

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

Input

第一行正整数N,M,QN,M,Q 。
接下来的MM行，每行ai,bi,cia_i,b_i,c_i，表示有一条从aia_i到bib_i，边权为cic_i的有向道路。保证不会有自环，但不保证没有重边。
接下来QQ行，每行一个CC，表示询问当每次费用为CC时的最小答案。

Output

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

Sample Input

1
2
3
4
5
6
7
8
9
6 5 3
1 3 2
2 3 2
3 4 2
4 5 2
4 6 2
1
5
10

Sample Output

1
2
3
6
21
32

HINT

样例说明
第一年的时候，CC只有11。我们比较懒所以就不安排英雄出游了，需要支付66的费用。
第二年的时候，我们可以这么安排：
一个英雄1→3→4→51\to 3\to 4\to 5，需要付2+2+2=62+2+2=6的费用，同时还要花5费用打的回家。再花5+55+5的费用来补偿22号城市和66号城市。
第三年略。
数据范围
对于100%100\%的数据，2≤N≤2502\le N\le 250, 1≤M≤300001\le M\le 30000, 1≤Q≤100001\le Q\le 10000, 1≤ci≤100001\le c_i\le 10000, 1≤C≤100001\le C\le 10000。

标签：二分 费用流

Solution

比较难想但很奇妙的费用流建模。
题目可以转化为：选择若干条带权路径，选择指覆盖终点，所有没被覆盖的点都要付出CC的代价，每次给定CC求最小代价。
首先用FloyedFloyed算出多源最短路把每个点拆成入点和出点，建图：
S→aS\to a 容量11 费用00
a→b′a\to b' 容量11 费用disa,bdis_{a,b}
a′→Ta'\to T 容量11 费用00
每次增广均会有前面未覆盖的点被覆盖，即用增广一次的代价来代替CC。若增广前代价为WW，则增广后为W−C+costW-C+cost。记录每次增广增加的费用，可知这个费用是单增的，推得当 cost<Ccost < C 时，可增广使答案变小，而当 cost>Ccost > C 时，继续增广会使答案变大。因此对每个询问二分出 cost<Ccost < C 的分界点计算答案即可。

Code

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
#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;
}