ABC318-D

问题陈述

给你一个加权无向完整图，图中有 𝑁N 个顶点，编号从 11 到 𝑁N 。连接顶点 𝑖i 和 𝑗j 的边 (𝑖<𝑗)(i<j) 的边的长度与 (𝑖<𝑗)(i<j) 的长度相同。 (𝑖<𝑗)(i<j) 的边的权重为 𝐷𝑖,𝑗Di,j​ 。

在以下条件下选择若干条边时，请找出所选边的最大可能总重量。

• 所选边的端点是成对不同的。

限制因素

• 2≤𝑁≤162≤N≤16
• 1≤𝐷𝑖,𝑗≤1091≤Di,j​≤109
• 所有输入值均为整数。

N 
𝐷1,2D1,2​ 𝐷1,3D1,3​ …… 𝐷1,𝑁D1,N​
𝐷2,3D2,3​ …… 𝐷2,𝑁D2,N​
⋮⋮
𝐷𝑁−1,𝑁DN−1,N​

做法

一看数据范围就想到dfs爆搜（我居然又没想到qaq）。我写的，超时了

#include<bits/stdc++.h>
using namespace std;
int n;
int vis[20];
long long d[20][20];
long long ans;
void dfs(long long sum){
    for(int i=1;i<=n;i++){
        for(int j=x+1;j<=n;j++){
            if(!vis[i]&&!vis[j]){
                vis[i]=1,vis[j]=1;
                ans=max(ans,sum+d[i][j]);
                dfs(x+1,sum+d[i][j]);
                vis[i]=0,vis[j]=0;
            }
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            scanf("%lld",&d[i][j]);
        }
    }
    dfs(0);
    cout<<ans; 
}

正解

#include<bits/stdc++.h>
using namespace std;
int n;
int vis[20];
long long d[20][20];
long long ans;
void dfs(int x,long long sum){
    if(x>n){
        ans=max(sum,ans);
        return ;
    }
    if(!vis[x]){
        vis[x]=1;
        for(int i=x+1;i<=n;i++){
            if(!vis[i]) {
                vis[i]=1;
                dfs(x+1,sum+d[x][i]);
                vis[i]=0;
            }
        }
        vis[x]=0;
    }
    dfs(x+1,sum);//跳过这个点 
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            scanf("%lld",&d[i][j]);
        }
    }
    dfs(1,0);
    cout<<ans; 
}

 答案的搜法和我想的有点不一样，我的太暴力了，我又想不到怎么优化qaq。