【每日一题】Rinne Loves Edges（最小割）

题目大意：
割掉权值和最小的边，使得根节点s与度为1的点都没有连边。

Solution:
关于割边问题，我们很容易想到最小割，又有最大流=最小割，可以直接上dinic了。
建一个超级源点，连接所有度为1的边（根节点除外），容量为INF，s为汇点，然后跑dinic求出最大流即为答案。
网络流度理论时间复杂度一直都很玄学，但实际上跑起来的速度是很快的。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
const ll N = 2e6 + 5;
const ll INF = 0x3fffffffffffff;

ll to[N], f[N], ne[N], h[N], idx;
ll n, m, s, de[N], dp[N];

void add(ll a, ll b, ll c) {
  to[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;
  to[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

ll dfs(ll now, ll flow, ll t) {
  if (now == t) return flow;
  ll sum = 0;
  for (ll i = h[now]; i != -1 && flow; i = ne[i]) {
    if (f[i] && dp[to[i]] == dp[now] + 1) {
      ll x = dfs(to[i], min(flow, f[i]), t);
      f[i] -= x, f[i ^ 1] += x, flow -= x, sum += x;
    }
  }
  if (!sum) dp[now] = -2;
  return sum;
}

bool bfs(ll s, ll t) {
  queue<int> q;
  memset(dp, 0, sizeof(dp));
  dp[s] = 1;
  q.push(s);
  while (!q.empty()) {
    ll x = q.front();
    q.pop();
    for (ll i = h[x]; i != -1; i = ne[i]) {
      if (f[i] && !dp[to[i]]) {
        q.push(to[i]);
        dp[to[i]] = dp[x] + 1;
        if (to[i] == t) return true;
      }
    }
  }
  return false;
}

ll dinic(ll s, ll t) {
  ll res = 0;
  while (bfs(s, t)) res += dfs(s, INF, t);
  return res;
}

int main() {
  memset(h, -1, sizeof(h));
  scanf("%lld%lld%lld", &n, &m, &s);
  for (ll i = 1; i <= m; i++) {
    ll x, y, z;
    scanf("%lld%lld%lld", &x, &y, &z);
    add(x, y, z);
    add(y, x, z);
    de[x]++;
    de[y]++;
  }
  for (ll i = 1; i <= n; i++) {
    if (de[i] == 1 && i != s) add(0, i, INF);
  }
  printf("%lld\n",dinic(0, s));
  return 0;
}