问题陈述
给你一个加权无向完整图,图中有 𝑁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。