5 条题解

  • 2
    @ 2014-10-19 22:06:30

    设第i天是否去逛街为a[i],c[i]表示第i天的智商,a[i]=1表示去逛街,a[i]=0表示不去
    则可得2n个不等式
    a[1]+a[2]+...+a[n]<=k
    a[2]+a[3]+...+a[n+1]<=k
    ...
    a[2n+1]+....+a[3n]<=k
    求c[1]*a[1]+c[2]*a[2]+...+c[3n]*a[3n]的最大值
    添加一个辅助变量
    a[1]+a[2]+...+a[n]+y[1]=k
    a[2]+a[3]+...+a[n+1]+y[2]=k
    ...
    a[2n+1]+....+a[3n]+y[2n+1]=k
    0<=y[i]<=k
    将上述不等式相邻两个相减
    y[1]+a[1]=a[n+1]+y[2]。。。。。。。。。1
    y[2]+a[2]=a[n+2]+y[3]。。。。。。。。。2
    ......
    y[n+1]+a[n+1]=a[2n+1]+y[n+2]。。。。。。。n+1
    ......
    y[2n]+a[2n]=a[3n]+y[2n+1]。。。。。。。。2n
    根据网络中每个节点流入量等于流出量的性质
    将上述等式编号并抽象成网络中的点,变量a[i]和y[i]抽象为网络中的有向边(弧)
    问题等价于求最大费用最大流
    以a[n+1]为例 可以看成是节点1部分流出量和节点n+1的部分流入量于是可以建边从n+1到1
    故根据这些等式可以建图
    设源点为0,汇点为2n+3
    i到n+i连一条弧,流量上限为1,费用为c[n+i] 1<=i<=n
    i到i+1连一条弧,流量上限为k,费用为0(即为辅助变量y)1<=i<=2n-1
    这时发现题目的k还没用上,
    于是发现上述等式成立必需满足这两个等式
    a[1]+a[2]+...+a[n]+y[1]=k。。。。。2n+1
    a[2n+1]+....+a[3n]+y[2n+1]=k。。。。。2n+2
    于是建一个节点2n+1
    为了满足2n+1式
    则由源点向节点2n+1连一条流量上限为k的边,费用为0。
    由节点2n+1向i连一条流量上限为1的边,费用为c[i](即为变量a[i])1<=i<=n
    由2n+1向1连一条流量上限为k的边,费用为0(即y[1])
    同理建一个节点2n+2
    为了满足2n+2式则由节点2n+2向汇点连一条流量上限为k的边,费用为0。
    由节点i向2n+2连一条流量上限为1的边,费用为ci
    建图完毕,剩下就是套算法。

    • @ 2017-09-05 14:18:41

      题主最后建关于点2n+2的方法有错吧·····

  • 1
    @ 2018-03-21 17:13:41

    我有个不用线性规划的做法,简单费用流。

    类似于网络流24题中的最长k可重区间集问题,将每个点拆成ii'SSS连容量为k费用为0的边,SS向每个点i连容量为1费用为0的边,每个ii'连容量为1费用为价值的边,每个i'T连容量为1费用为0的边,i'[i+n,i+n*3]中的所有点连容量为1费用为0的边,跑最大费用流。

    代码

    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <queue>
    #include <vector>
    
    typedef long long ll;
    const int N = 1205;
    const ll INF = 1e18;
    
    int read() {
        int x = 0, f = 1;
        char c = getchar();
        while (!isdigit(c)) {
            if (c == '-') f = -1;
            c = getchar();
        }
        while (isdigit(c)) {
            x = (x << 3) + (x << 1) + (c ^ 48);
            c = getchar();
        }
        return x * f;
    }
    
    ll min(ll x, ll y) {
        if (x <= y) return x; return y;
    }
    
    struct Edge {
        int from, to; ll flow, cap, cost;
    };
    std::vector<Edge> edges;
    std::vector<int> G[N];
    int S, SS, T, n, p[N]; ll d[N], a[N];
    
    void addedge(int from, int to, ll cap, ll cost) {
        edges.push_back((Edge){from, to, 0, cap, cost});
        edges.push_back((Edge){to, from, 0, 0, -cost});
        int size = edges.size();
        G[from].push_back(size - 2);
        G[to].push_back(size - 1);
    }
    
    bool SPFA(ll &flow, ll &cost) {
        bool inq[N] = {}; inq[S] = 1;
        std::queue<int> Q; Q.push(S);
        for (int i = 0; i < n; ++ i) d[i] = INF;
        d[S] = p[S] = 0, a[S] = INF;
        while (!Q.empty()) {
            int u = Q.front(); Q.pop(), inq[u] = 0;
            int size = G[u].size();
             for (int i = 0; i < size; ++ i) {
                Edge e = edges[G[u][i]];
                if (e.cap > e.flow && d[e.to] > d[u] + e.cost) {
                    d[e.to] = d[u] + e.cost;
                    p[e.to] = G[u][i];
                    a[e.to] = min(a[u], e.cap - e.flow);
                    if (!inq[e.to]) Q.push(e.to), inq[e.to] = 1;
                }
            }
        }
        if (d[T] == INF) return false;
        flow += a[T], cost += a[T] * d[T];
        int x = T;
        while (x != S) {
            edges[p[x]].flow += a[T], edges[p[x]^1].flow -= a[T];
            x = edges[p[x]].from;
        }
        return true;
    }
    
    ll mincost() {
        ll flow = 0, cost = 0;
        while (SPFA(flow, cost)) {}
        return cost;
    }
    
    int main() {
        n = read(); int k = read(); S = 0, SS = n * 6 + 1, T = SS + 1;
        addedge(S, SS, k, 0);
        for (int i = 1; i <= n * 3; ++ i) {
            int x = read();
            addedge(SS, i, 1, 0);
            addedge(i, i + n * 3, 1, -x);
            addedge(i + n * 3, T, 1, 0);
            for (int j = i + n; j <= n * 3; ++ j)
                addedge(i + n * 3, j, 1, 0);
        }
        n = T + 1;
        printf("%lld\n", -mincost());
        return 0;
    }
    
  • 0
    @ 2014-10-19 23:13:33

    这一题用线性规划可破。

  • 0
    @ 2014-10-18 22:04:43

    直接网络流

    • @ 2014-10-19 11:12:37

      是按上面那个人说的建图吗?

  • 0
    @ 2014-10-18 21:58:11

    我提前发题解了

  • 1

信息

ID
1891
难度
6
分类
(无)
标签
(无)
递交数
320
已通过
95
通过率
30%
被复制
5
上传者