题解：P12593 沉石鱼惊旋

· · 题解

Solution

今天比赛挂分了，写篇题解弥补一下吧。

这道题要求我们找到一个删除图中所有节点的顺序，使得删除过程中的总代价最小。每次删除一个节点时，代价是与该节点相连且未被删除的边的权值之和乘以这些边的数量。

开题时先看数据范围。我们发现 n≤8，所以我们可以枚举全排列枚举删除顺序。使用打删除标记遍历每一条边来模拟题意。

至于枚举全排列可以使用 next_permutation 生成所有节点的排列顺序，每一种排列代表一种可能的删除顺序。，不会用的也可以用 DFS 搜索（同理）。

模拟删除的过程可以用维护一个数组 d 来记录哪些节点已经被删除。

对于当前要删除的节点 u，统计与 u 相连且未被删除的边的数量 cnt 和这些边的权值之和 s。

再计算本次操作的代价 cnt \times s，并累加到总代价中。

然后标记节点 u 为已删除。

最后在所有排列对应的总代价中，记录最小的那个。

本题解使用数组实现，没学过树的同学可以看看。

code

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[103][103],b[103][103],c[130],x,y,z,e=1e18;
bool d[103];
int main() 
{
    cin>>n>>m;
    for(int i=0;i<m;i++) 
    {
        cin>>x>>y>>z;
        a[x][y]=a[y][x]=1;//
标记边是否存在
        b[x][y]=b[y][x]=z;//存储边的权值
    }
    for(int i=0;i<n;i++) 
        c[i]=i+1;//初始化排列数组
    while(next_permutation(c,c+n))//生成下一个全排列
    {
        for(int i=1;i<=n;i++) 
            d[i]=false;//重置删除标记
        long long summ=0;
        for(int i=0;i<n;i++)
        {
            long long u=c[i],cnt=0,s=0;
            for(int j=1;j<=n;j++) 
                if(a[u][j]&&!d[j]) cnt++,s+=b[u][j];//统计边数和权值和
            summ+=cnt*s;//累加代价
            d[u]=true;//标记为已删除
        }
        e=min(summ,e);//更新最小代价
    } 
    cout<<e;
    return 0;
}