题解 P4153 【[WC2015]k小割】

wlzhouzhuan · 2020-12-30 11:16:19 · 题解

WC2015 T1 k小割

• 吐槽

写了 2 个小时， 7.5KB 。。。

这题在 uoj 上被叉的吐血。。。最终终于通过了。官方数据是真的水。

• 题解

首先这题是三合一。

• 1\le n\le 10,1\le m\le 20,1\le k\le 10^6

哇 K 好大，怎么办？

注意到边只有 20 条，暴力枚举割不割，然后判断 S 和 T 的连通性即可。

时间复杂度 O(2^m\times n)

• 1\le n\le 150000,m=2n-4$ 且保证边是 $(1,i)$ 或 $(i,T)

画出来发现是一个 S 连向 n-2 个点再连向 T 的三分图，对于第二层的点 i ，记 S 连向它的权值为 x ，它连向 T 的权值为 y 。

不失一般性，令 x\le y ，则这个点的取法有三个阶段：取 x ；取 y ；取 x+y 。我们可将其视为依次加 x , y-x , x ，记为三元组 a_i=(a_{i,0},a_{i,1},a_{i,2})

每个点初始的贡献是 x ，按照第二关键字排序。用 pq 维护它们，有三种转移状态：

• 当前点“升级”：从 a_{i,1} 过渡到 a_{i,2} ；

• 当前点“降级”，并前往下一个点：从 a_{i,2} 到 a_{i,1} ，并新加入 a_{i+1,1} ；

• 直接前往下一个点：新加入 a_{i+1,1}

可以发现这样 pq 内的状态数是 O(n) 的。

故时间复杂度 O(nlogn) 。

• 1\le n\le 50,1\le m\le 1500,1\le k\le 100

不妨先考虑如何求次小割。

先跑出最大流，并抠出割边，则次小割有两种可能：

• 将某一条割边改成次小的割边；

• 新加入一条边；

前者可以通过将割边的两端点在残余网络上重新跑最小割得到，后者直接枚举非割边里的最小流量的边即可。

因此求次小割的复杂度也是 O(m\times flow) 的。

类似地，引入 must[i],stop[i] 表示这条边必须选/禁止选，那就可以将上面求次小割的过程推广到 k 小割，用 pq 维护整个过程即可。

实现起来难度极大。。。

时间复杂度 O(m\times flow\times klogk) ，最坏情况 O(nm^2klogk) ，但网络流部分跑不满。

建议写完以后到 UOJ 上测一测， hack 数据特别多。。。

// Author: wlzhouzhuan
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pb push_back
#define fir first
#define sec second
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, t) memset(s, t, sizeof(s))
#define mcpy(s, t) memcpy(s, t, sizeof(t))
template<typename T1, typename T2> void ckmin(T1 &a, T2 b) { a > b && a = b; }
template<typename T1, typename T2> void ckmax(T1 &a, T2 b) { a < b && a = b; }
int read() {
  int x = 0, f = 0; char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
template<typename T> void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template<typename T> void print(T x, char let) {
  print(x), putchar(let);
}

const int N = 300005;
const int inf = 5e8;
int n, m, S, T, K;
int _U[N], _V[N], _W[N];

namespace BRUTE {
struct E {
  int u, v, w;
} e[N];
vector<int> adj[N];
int vis[N];
void dfs(int u) {
  vis[u] = 1;
  for (auto v: adj[u]) {
    if (!vis[v]) dfs(v);
  }
}
int f[N];
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
void MAIN() {
  for (int i = 1; i <= m; i++) {
    e[i].u = _U[i], e[i].v = _V[i], e[i].w = _W[i];
  }
  vector<ll> ans;
  for (int st = 0; st < 1 << m; st++) {
    for (int i = 1; i <= n; i++) vis[i] = 0, adj[i].clear();
    ll coef = 0;
    for (int i = 1; i <= m; i++) {
      if (st >> (i - 1) & 1) {
        coef += e[i].w;
      } else {
        adj[e[i].u].pb(e[i].v);
      }
    }
    dfs(S);
    if (!vis[T]) ans.pb(coef);
  }
  sort(ans.begin(), ans.end());
  for (int i = 0; i < min(int(ans.size()), K); i++) {
    printf("%lld\n", ans[i]);
  }
  if (K > ans.size()) puts("-1");
}
}

namespace SP {
struct node {
  int x, y;
  friend bool operator < (const node &x, const node &y) {
    if (x.x ^ y.x) return x.x < y.x;
    else return x.y < y.y;
  }
} a[N];
int cnt = 0;
struct PQ {
  ll ans;
  int pos, opt;
  friend bool operator < (const PQ &x, const PQ &y) {
    return x.ans > y.ans;
  }
};
priority_queue<PQ> pq; 
void MAIN() {
  for (int i = 1; i <= m; i++) {
    int u = _U[i], v = _V[i], w = _W[i];
    if (v == S) swap(u, v);
    if (v == T) swap(u, v);
    if (u == S) a[v].x = w;
    else a[v].y = w;
  }
  ll ans = 0;
  for (int i = 1; i <= n; i++) {
    if (i == S || i == T) continue;
    a[++cnt] = a[i];
    if (a[cnt].x > a[cnt].y) swap(a[cnt].x, a[cnt].y);
    ans += a[cnt].x;
    int tmp = a[cnt].x;
    a[cnt].x = a[cnt].y - a[cnt].x, a[cnt].y = tmp;
  }
  sort(a + 1, a + cnt + 1);
  printf("%lld\n", ans), K--;
  pq.push({ans + a[1].x, 1, 1});
  while (K-- && !pq.empty()) {
    PQ u = pq.top(), v; pq.pop();
    printf("%lld\n", u.ans);
    if (u.opt == 1) { // 升级
      v.pos = u.pos, v.opt = 2, v.ans = u.ans + a[v.pos].y;
      pq.push(v); 
    }
    if (u.opt == 1 && u.pos < n) { // 退级，往前一格 
      v.pos = u.pos + 1, v.opt = 1, v.ans = u.ans - a[u.pos].x + a[v.pos].x;
      pq.push(v);
    }
    if (u.pos < n) { // 直接往前一格 
      v.pos = u.pos + 1, v.opt = 1, v.ans = u.ans + a[v.pos].x;
      pq.push(v);
    }
  }
  if (K > 0) puts("-1");
}
}

namespace FLOW {
struct Graph {
  struct Edge {
    int to, nxt, cap;
  } edge[3005];
  int head[55], h[55], tot = 1;
  void add(int u, int v, int cap) {
    edge[++tot] = {v, head[u], cap};
    head[u] = tot;  
  }
  void addedge(int u, int v, int cap) {
    add(u, v, cap), add(v, u, 0);
  }
  int dep[55];
  bool bfs(int S, int T) {
    queue<int> q;
    for (int i = 1; i <= n; i++) dep[i] = -1, h[i] = head[i];
    dep[S] = 0, q.push(S);
    while (!q.empty()) {
      int u = q.front(); q.pop();
      for (int i = head[u]; i; i = edge[i].nxt) {
        int v = edge[i].to, cap = edge[i].cap;
        if (dep[v] == -1 && cap) {
          dep[v] = dep[u] + 1;
          if (v == T) return 1;
          q.push(v);
        }
      }
    }
    return dep[T] != -1;
  }
  int dfs(int u, int T, int ans) {
    if (u == T) return ans;
    int over = 0;
    for (int &i = h[u]; i; i = edge[i].nxt) {
      int v = edge[i].to, cap = edge[i].cap;
      if (dep[v] == dep[u] + 1 && cap) {
        int res = dfs(v, T, min(ans, cap));
        ans -= res, over += res;
        edge[i].cap -= res, edge[i ^ 1].cap += res;
        if (!res) dep[v] = -1;
        if (!ans) break;
      }
    }
    return over;
  }
  int ans;
  int Dinic(int S, int T) {
    ans = 0;
    while (bfs(S, T)) {
      ans += dfs(S, T, inf);
      if (ans >= inf) break;
    }
    return ans;
  }
  int vis[55], in[1505];
  void DFS(int u) {
    vis[u] = 1;
    for (int i = head[u]; i; i = edge[i].nxt) {
      int v = edge[i].to, cap = edge[i].cap;
      if (!vis[v] && cap) DFS(v);
    }
  }
  void get_cut() {
    for (int i = 1; i <= n; i++) vis[i] = in[i] = 0;
    DFS(S);
    for (int i = 1; i <= m; i++) {
      if (vis[_U[i]] && !vis[_V[i]]) {
        in[i] = 1;
      }
    }
  }
} G, G1, G2;

struct node {
  int visx[55], visy[55];
  int must[1505], stop[1505];
  int ans, id;
  friend bool operator < (const node &x, const node &y) {
    return x.ans > y.ans;
  }
  void run() {
    G1 = G, ans = id = 0;
    for (int i = 1; i <= m; i++) {
      if (must[i]) ans += G1.edge[i << 1].cap, G1.edge[i << 1].cap = G1.edge[i << 1 | 1].cap = 0;
      if (stop[i]) G1.edge[i << 1].cap = inf, G1.edge[i << 1 | 1].cap = 0; 
    }
    ans += G1.Dinic(S, T);
//    printf("current ans = %d\n", ans);
    G1.get_cut();
    int ext = inf;
    for (int i = 1; i <= n; i++) visx[i] = visy[i] = 0;
    for (int i = 1; i <= m; i++) {
      if (must[i] || stop[i]) continue;
      if (G1.in[i]) { // 割边 
        if (!visx[_U[i]]) {
          visx[_U[i]] = 1;
          G2 = G1;
          int ext_flow = G2.Dinic(S, _U[i]);
          if (ext_flow < ext) ext = ext_flow, id = i;
        }
        if (!visy[_V[i]]) {
          visy[_V[i]] = 1;
          G2 = G1;
          int ext_flow = G2.Dinic(_V[i], T);
          if (ext_flow < ext) ext = ext_flow, id = i; 
        }
      } else if (_W[i] < ext) {
        ext = _W[i], id = i;
      } 
    }
    ans += ext;
  }
} a, b;
priority_queue<node> pq;

void MAIN() {
  for (int i = 1; i <= m; i++) {
    G.addedge(_U[i], _V[i], _W[i]);
  }
  G1 = G;
  G1.Dinic(S, T), K--;
  printf("%d\n", G1.ans);
  a.run();
  if (a.ans < inf) pq.push(a);
  while (K-- && !pq.empty()) {
    node u = pq.top(); pq.pop();
    printf("%d\n", u.ans);
//    printf("now u = (%d, %d)\n", u.ans, u.id);
    a = u, a.must[a.id] = 1, a.run();
//    printf("u -> a = (%d, %d)\n", a.ans, a.id);
    if (a.ans < inf) pq.push(a);
    b = u, b.stop[b.id] = 1, b.run();
//    printf("u -> b = (%d, %d)\n", b.ans, b.id);
    if (b.ans < inf) pq.push(b);
  }
  if (K > 0) puts("-1");
}
}

int main() {
  n = read(), m = read(), S = read(), T = read(), K = read();
  int ok = 0;
  set<int> s;
  for (int i = 1; i <= m; i++) {
    _U[i] = read(), _V[i] = read(), _W[i] = read();
    if (_U[i] == S && _V[i] != T) ok++, s.insert(2 * _V[i]);
    else if (_V[i] == S && _U[i] != T) ok++, s.insert(2 * _U[i]);
    else if (_U[i] == T && _V[i] != S) ok++, s.insert(2 * _V[i] + 1);
    else if (_V[i] == T && _U[i] != S) ok++, s.insert(2 * _U[i] + 1);
  }
  if (m <= 24) BRUTE::MAIN(), exit(0);
  if (ok == m && s.size() == 2 * n - 4) SP::MAIN(), exit(0);
  FLOW::MAIN(), exit(0);
  return 0;
}