【洛谷P3749】[六省联考2017]寿司餐厅（网络流）

洛谷

题意：

给出\(n\)份寿司，现可以选取任意多次连续区间内的寿司，对于区间\([l,r]\)，那么贡献为\(\sum_{i=l}^r \sum_{j=i}^rd_{i,j}\)（对于相同的\(d_{i,j}\)只会计算一次）。

每种寿司都有一个标签\(a_i\)，若选了\(c\)种标签为\(a_i\)的寿司，此时花费\(ma_i^2+ca_i\)。

问最终最大价值为多少。

思路：

(最小割，费用流这两个东西傻傻分不清楚...)

因为对于任意一个区间\([l,r]\)，其选择过后，内部区间贡献都要算上，并且每种贡献只算一次。这种严格先后关系并且要求不计算重复的问题，考虑最大权闭合子图。
我们将每个\(d_{i,j}\)抽象成点来建立有向图，易知\(d_{i,j}\)向\(d_{i+1,j},d_{i,j-1}\)连边，权值即为\(d_{i,j}\)。
考虑如何处理\(ma_i^2+ca_i\)：对于标签为\(a_i\)的寿司，我们每选一种，会多出\(c_i\)；如果选了标签为\(a_i\)，那么就会多出\(ma_i^2\)。所以对于每个\(d_{i,i}\)，直接向\(a_i\)连边，表示选了之后会有\(ma_i^2\)的贡献；同时，将\(d_{i,i}\)的权值减去\(a_i\)，这样即可处理\(ca_i\)。
有向图以及每个点的点权知道后，接下来就直接类似于最大权闭合子图那样建边即可。

代码如下：

/*

 * Author:  heyuhhh

 * Created Time:  2019/10/30 12:45:44

 */

#include <bits/stdc++.h>

#define MP make_pair

#define fi first

#define se second

#define sz(x) (int)(x).size()

#define all(x) (x).begin(), (x).end()

#define INF 0x3f3f3f3f

#ifdef Local

  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)

  void err() { std::cout << '\n'; }

  template<typename T, typename...Args>

  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }

#else

  #define dbg(...)

#endif

void pt() {std::cout << '\n'; }

template<typename T, typename...Args>

void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

//head

const int N = 2e4 + 5;

#define _S heyuhhh

template <class T>

struct Dinic{

    struct Edge{

        int v, next;

        T flow;

        Edge(){}

        Edge(int v, int next, T flow) : v(v), next(next), flow(flow) {}

    }e[N * 10];

    int head[N], tot;

    int dep[N];

    void init() {

        memset(head, -1, sizeof(head)); tot = 0;

    }

    void adde(int u, int v, T w, T rw = 0) {

        e[tot] = Edge(v, head[u], w);

        head[u] = tot++;

        e[tot] = Edge(u, head[v], rw);

        head[v] = tot++;

    }

    bool BFS(int _S, int _T) {

        memset(dep, 0, sizeof(dep));

        queue <int> q; q.push(_S); dep[_S] = 1;

        while(!q.empty()) {

            int u = q.front(); q.pop();

            for(int i = head[u]; ~i; i = e[i].next) {

                int v = e[i].v;

                if(!dep[v] && e[i].flow > 0) {

                    dep[v] = dep[u] + 1;

                    q.push(v);

                }

            }

        }

        return dep[_T] != 0;

    }

    T dfs(int _S, int _T, T a) {

        T flow = 0, f;

        if(_S == _T || a == 0) return a;

        for(int i = head[_S]; ~i; i = e[i].next) {

            int v = e[i].v;

            if(dep[v] != dep[_S] + 1) continue;

            f = dfs(v, _T, min(a, e[i].flow));

            if(f) {

                e[i].flow -= f;

                e[i ^ 1].flow += f;

                flow += f;

                a -= f;

                if(a == 0) break;

            }

        }

        if(!flow) dep[_S] = -1;

        return flow;

    }

    T dinic(int _S, int _T) {

        T max_flow = 0;

        while(BFS(_S, _T)) max_flow += dfs(_S, _T, INF);

        return max_flow;

    }

};

Dinic <int> solver;

int n, m;

int a[105], Id[105][105], F[105][105];

void run(){

    solver.init();

    int Max = 0;

    for(int i = 1; i <= n; i++) {

        cin >> a[i];

        Max = max(a[i], Max);

    }

    int cnt = 2;

    for(int i = 1; i <= n; i++) {

        for(int j = i; j <= n; j++) {

            cin >> F[i][j];

            Id[i][j] = ++cnt;

        }

    }

    int S = 1, T = 2;

    int ans = 0;

    for(int i = 1; i <= n; i++) {

        for(int j = i; j <= n; j++) {

            int cost = F[i][j];

            if(i == j) {

                if(m) solver.adde(Id[i][j], cnt + a[i], INF);

                cost -= a[i];

            } else {

                solver.adde(Id[i][j], Id[i][j - 1], INF);

                solver.adde(Id[i][j], Id[i + 1][j], INF);

            }

            if(cost > 0) solver.adde(S, Id[i][j], cost), ans += cost;

            else solver.adde(Id[i][j], T, -cost);

        }

    }

    for(int i = 1; i <= Max; i++) {

        solver.adde(++cnt, T, m * i * i);

    }

    dbg(1);

    ans -= solver.dinic(S, T);

    cout << ans << '\n';

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    cout << fixed << setprecision(20);

    while(cin >> n >> m) run();

	return 0;

}

巴特西

【洛谷P3749】[六省联考2017]寿司餐厅（网络流）

最新文章

热门文章