沉石鱼惊旋

# P12593 沉石鱼惊旋

## 题目背景

> 绝代有佳人，幽居在空谷。

## 题目描述

小 C 有一张 $n$ 个点 $m$ 条边的简单无向带权连通图 $G$。

现在你可以进行 $n$ 次操作，每次操作如下：

选择一个仍未被删除的点 $u$，然后删除点 $u$ 和当前与 $u$ 相连的所有边（即其中一个端点是 $u$ 的边）。假设本次删除的边的边权分别是 $w_1, w_2,\dots w_k$，则本次操作的代价是  $k\times (w_1+w_2+\dots+w_k)$。

你的总代价是这 $n$ 次操作的代价和。

显然 $n$ 次操作后，所有的边和点都将被删除。现在小 C 想知道，将图中所有点和边都删除（即把图删空）的最小总代价是多少。当然，在过程中你不需要保证图每次操作后仍然连通。

> 天寒翠袖薄，日暮倚修竹。

## 输入格式

第一行，两个整数 $n,m$。

接下来的 $m$ 行，每行 $3$ 个整数 $u,v,w$，表示 $u$ 和 $v$ 之间有一条边权为 $w$ 的边。

## 输出格式

一行，一个整数，表示删空图 $G$ 的最小代价。

## 输入输出样例 #1

### 输入 #1

```
6 8
1 3 10
1 5 20
1 6 30
2 5 10
2 6 20
3 4 30
3 5 10
5 6 20
```

### 输出 #1

```
240
```

## 说明/提示

在样例 1 中，这张图有 $8$ 条边：$(1,3,10),(1,5,20),(1,6,30),(2,5,10),(2,6,20),(3,4,30),(3,5,10),(5,6,20)$。一个可行的最优策略如下：

- 选择 $u=4$ 删除，花费 $1\times (30)=30$ 的代价。
- 选择 $u=3$ 删除，花费 $2\times (10+10)=40$ 的代价。
- 选择 $u=2$ 删除，花费 $2\times (10+20)=60$ 的代价。
- 选择 $u=5$ 删除，花费 $2\times (20+20)=80$ 的代价。
- 选择 $u=6$ 删除，花费 $1\times (30)=30$ 的代价。
- 选择 $u=1$ 删除，没有边，花费 $0$ 的代价。

故总代价为 $30+40+60+80+30+0=240$。

---

- 对于 $10\%$ 的数据，边权 $w=1$。
- 对于另外 $20\%$ 的数据，$m=n-1$。
- 对于 $100\%$ 的数据，$1\leq n\leq 8$，$n-1\leq m\leq \frac{n(n-1)}{2}$，$1\leq u,v\leq n$，$1\leq w\leq 10^9$。保证图中没有重边和自环。

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{ll v,w;
};
vector<node>g[30];
vector<bool>d(30);
vector<ll>a(30);
ll n,m;
ll ans=LLONG_MAX;
void dfs(ll step){if(step==n+1){vector<bool>del(30,false);ll res=0;for(ll i=1;i<=n;i++){ll u=a[i];ll cnt=0,sum=0;for(auto t:g[u]){if(!del[t.v]){cnt++;sum+=t.w;}}del[u]=true;res+=cnt*sum;}ans=min(ans,res);return ;}for(int i=1;i<=n;i++){if(!d[i]){d[i]=true;a[step]=i;dfs(step+1);d[i]=false;a[step]=0;}}
}
int main(){cin>>n>>m;for(int i=0;i<m;i++){ll u,v,w;cin>>u>>v>>w;g[u].push_back(node{v,w});g[v].push_back(node{u,w});}dfs(1);cout<<ans;return 0;
}