Codechef 12.1 CARDSHUF Splay
Codechef 13.9 TWOROADS 数学+计算几何+拉格朗日乘数法

Codechef 12.9 PARADE 最短路+Floyd+费用流

shinbokuow posted @ Dec 02, 2015 03:44:31 PM in Something with tags floyd 最短路 费用流 , 681 阅读

 

题目大意:
有一个$n$个点,$m$条边的有向图,边上是带权的,现在要找出若干条路径,首先花费所有路径上的边的权值之和(若某条边出现在$k$条路径中则计算$k$次),随后如果有一条路径的起点和终点不同额外花费$C$的费用,如果有一个点没有出现在任意一条路径中额外花费$C$的费用。现有$Q$组询问,每次给定一个$C$的取值,问这种情况下的最小花费。
数据范围$n\leq{250},m\leq{30000}$。
算法讨论:
我们用Floyd算法求出全局最短路,然后重新建图,将每两个点之间连一条边,边权为两个点之间的最短路。然后,我们在新图上求解这个问题,那么可以将问题转化为选出一些点不相交的路径,若路径上一共有$k$条边,则付出的费用为所有边的权值之和再加上$(n-k)\times{C}$。
那么这个问题类似于有向图的最小路径覆盖问题,我们将所有点拆成入点和出点,然后利用SPFA求最小费用流,那么每次增广选择的边的权值都是单调递增的,我们将这些权值记下来,那么对于一个给定的$C$,我们可以二分找到第一个$>C$的权值,只选择这个权值前面的权值对应的边。
时空复杂度:
时间复杂度$O(n^3+COSTFLOW(n,n^2)+Q\log n)$,空间复杂度$O(n^2)$。
代码:
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define inf 0x1f1f1f1f
#define N 260
int f[N][N], ans[N], num;
struct Solver {
    static const int V = 510;
    static const int E = 1000010;
    int head[V], nxt[E], to[E], flow[E], cost[E], ind;
    int d[V], ld[V], lb[V];
    bool inq[V];
    void reset() {
        ind = 0;
        memset(head, -1, sizeof head);
    }
    void addedge(int a, int b, int f, int c) {
        int q = ind++;
        to[q] = b;
        nxt[q] = head[a];
        head[a] = q;
        flow[q] = f;
        cost[q] = c;
    }
    void make(int a, int b, int f, int c) {
        //printf("%d %d %d %d\n", a, b, f, c);
        addedge(a, b, f, c);
        addedge(b, a, 0, -c);
    }
    bool spfa(int s, int t) {
        static queue<int> q;
        static int i, j;
        memset(d, 0x1f, sizeof d);
        memset(inq, 0, sizeof inq);
        d[s] = 0;
        inq[s] = 1;
        q.push(s);
        while (!q.empty()) {
            i = q.front();
            q.pop();
            inq[i] = 0;
            for (j = head[i]; j != -1; j = nxt[j]) {
                if (flow[j] && d[to[j]] > d[i] + cost[j]) {
                    ld[to[j]] = i;
                    lb[to[j]] = j;
                    d[to[j]] = d[i] + cost[j];
                    if (!inq[to[j]]) {
                        q.push(to[j]);
                        inq[to[j]] = 1;
                    }
                }
            }
        }
        return d[t] != inf;
    }
    void minCost(int s, int t) {
        int i, mn;
        while (spfa(s, t)) {
            for (i = t, mn = inf; i != s; i = ld[i])
                mn = min(mn, flow[lb[i]]);
            for (ans[++num] = d[t] * mn, i = t; i != s; i = ld[i]) {
                flow[lb[i]] -= mn;
                flow[lb[i] ^ 1] += mn;
            }
        }
    }
}g;
int main() {
    //freopen("tt.in", "r", stdin);
    int n, m, q, i, j, k, a, b, c;
    cin >> n >> m >> q;
    memset(f, 0x1f, sizeof f);
    while (m--) {
        scanf("%d%d%d", &a, &b, &c);
        f[a][b] = min(f[a][b], c);
    }
    for (i = 1; i <= n; ++i)
        f[i][i] = 0;
    for (k = 1; k <= n; ++k)
        for (i = 1; i <= n; ++i)
            for (j = 1; j <= n; ++j)
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
    g.reset();
    int s = 0, t = 2 * n + 1;
    for (i = 1; i <= n; ++i) {
        g.make(s, 2 * i - 1, 1, 0);
        g.make(2 * i, t, 1, 0);
    }
    for (i = 1; i <= n; ++i)
        for (j = 1; j <= n; ++j)
            if (i != j && f[i][j] != inf)
                g.make(2 * i - 1, 2 * j, 1, f[i][j]);
    g.minCost(s, t);
    
    int cnt, res;
    while (q--) {
        scanf("%d", &c);
        for (cnt = res = 0, i = 1; i <= num; ++i) {
            if (ans[i] <= c) {
                ++cnt;
                res += ans[i];
            }
            else
                break;
        }
        printf("%d\n", res + (n - cnt) * c);
    }
    
    return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter