NC22598 Rinne Loves Edges

题目地址：

https://ac.nowcoder.com/acm/problem/22598

基本思路：

其实我没有看清楚条件QAQ这个图居然是一棵树(居然只在数据范围里写明了),那树形dp可以写而且更快,不过这里还是提供最小割的写法,毕竟这个无脑下面两个解法都提供了;

解法一：

1. 由于我们知道这个图实际上是一个树,所以我们把s当做它的根然后我们要使每个叶子节点都不能到达根;
2. 设f[u]表示使叶子节点不能到以u为根的树需要删除的最小边的代价;
3. 那么可以得到递推式 f[u] += min(f[to], edge[i].val),将叶子节点设为INF,就能递推出答案;
4. 复杂度: O(n) 跑了50多ms。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#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, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 1e18
inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
const int maxn = 1e5 + 10;
struct Edge{
    int to,next,val;
}edge[maxn];
int n,m,s;
int cnt = 0,head[maxn],f[maxn],du[maxn];
void add_edge(int u,int v,int w){
  edge[++cnt].next = head[u];
  edge[cnt].to = v;
  edge[cnt].val = w;
  head[u] = cnt;
}
void dfs(int u,int p) {
  if (du[u] == 1 && u != s) {//为叶子节点;
    f[u] = INF;//设为INF;
    return;
  }
  for (int i = head[u]; i != -1; i = edge[i].next) {
    int to = edge[i].to;
    if (to != p) {
      dfs(to, u);
      f[u] += min(f[to], edge[i].val);//递推;
    }
  }
}
signed main() {
  IO;
  cin >> n >> m >> s;
  mset(head, -1);
  rep(i, 1, m) {
    int u, v, w;
    cin >> u >> v >> w;
    add_edge(u, v, w);
    add_edge(v, u, w);
    du[u]++, du[v]++;
  }
  dfs(s, 0);
  cout << f[s] << endl;
  return 0;
}

解法二：

1. 看到的第一眼应该就能想到最小割应该是能写(但Dinic算法复杂度可能有点玄学),没学过最大流最小割的同学可以去先学习一下;
2. 我们找一个超级源点t连接所有度为1(不包括s)的顶点并将容量设为INF,然后根据最大流最小割原理 t->s 跑一遍最大流Dinic算法就行了,这里的Dinic算法用的白书上的模板。
3. 也只跑了250多ms,理论上最慢复杂度O(mn^2)不过树形图肯定跑不到这么慢。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#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, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 1e18
inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
const int maxn = 1e5 + 10;
struct edge{ int to,cap,rev ;};
vector<edge> G[maxn];
int level[maxn],iter[maxn];
void add_edge(int from,int to,int cap){
  G[from].push_back((edge){to,cap,G[to].size()});
  G[to].push_back((edge){from,0,G[from].size() - 1});
}
void bfs(int s){
  mset(level,-1);
  queue<int> que;
  level[s] = 0;
  que.push(s);
  while (!que.empty()){
    int v = que.front();que.pop();
    for(int i = 0 ; i < G[v].size() ; i++){
      edge &e = G[v][i];
      if(e.cap > 0 && level[e.to] < 0){
        level[e.to] = level[v] + 1;
        que.push(e.to);
      }
    }
  }
}
int dfs(int v,int t,int f){
  if(v == t) return f;
  for(int &i = iter[v] ; i < G[v].size() ; i++){
    edge &e = G[v][i];
    if(e.cap > 0 && level[v] < level[e.to]){
      int d = dfs(e.to,t,min(f,e.cap));
      if(d > 0){
        e.cap -=d;
        G[e.to][e.rev].cap +=d;
        return d;
      }
    }
  }
  return 0;
}
int max_flow(int s,int t) {
  int flow = 0;
  for (;;) {
    bfs(s);
    if (level[t] < 0) return flow;
    mset(iter, 0);
    int f;
    while ((f = dfs(s, t, INF)) > 0) {
      flow += f;
    }
  }
}
int n,m,s,du[maxn];
signed main() {
  n = read(), m = read(), s = read();
  rep(i, 1, m) {
    int u, v, w;
    u = read(), v = read(), w = read();
    add_edge(u, v, w);
    add_edge(v, u, w);
    du[u]++, du[v]++; //记录度;
  }
  //注意INF设大一点;
  rep(i, 1, n) {
    if (du[i] == 1 && i != s) {
      add_edge(0, i, INF);//将0作为超级源点;
    }
  }
  int ans = max_flow(0, s);
  print(ans);
  return 0;
}