这题不是图论吗……
by 1jia1 @ 2016-09-27 21:16:37
@[chenleyu](/space/show?uid=14381) 可是本题标签是搜索啊。。。
by zclzslz @ 2016-09-27 21:21:35
哦，那发个递推吧
by 1jia1 @ 2016-09-27 21:24:09
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int ga[41][41];
int n, i, j;
int minv, m;
bool visited[41];
void init()
{
cin >> n;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
cin >> ga[i][j];
memset(visited, false, sizeof(visited));
minv = 99999999;
m = 0;
}
void search(int step, int cur_node)
{
int i, j, k;
if (step == n)
{
if (m + ga[cur_node][1] < minv)
minv = m + ga[cur_node][1];
}
else
for (i=2; i<=n; i++)
{
if (i!=cur_node && !visited[i])
{
m += ga[cur_node][i];
visited[cur_node] = true;
if (m < minv)search(step+1,i);
m = m - ga[cur_node][i];
visited[cur_node] = false;
}
}
}
void print()
{
cout << minv<<endl;
fclose(stdout);
}
int main()
{
init();
search(1,1);
print();
return 0;
}
```
by 玉环妹妹 @ 2017-01-25 14:37:42
80分
#9，#10超时
by 玉环妹妹 @ 2017-01-25 14:38:13
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=20+10,INF=1000000000;
int List[maxn][maxn],p[maxn],a[maxn][maxn],n,ans=INF,sum,mins=INF;
void dfs(int q,int sum,int x){
if(q==n&&a[x][1]){
ans=min(ans,sum+a[x][1]);
return;
}
for(int i=1;i<=n;i++){
int k=List[x][i];
if(!p[k]){
if(sum+a[x][k]>=ans)return;
if(sum+n-q+mins+a[x][k]>=ans)return;
p[k]++;
dfs(q+1,sum+a[x][k],k);
p[k]--;
}
}
}
int main(){
int m,i,j,k,x,y,z;
freopen("Seller.in","r",stdin);
freopen("Seller.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
scanf("%d",&a[i][j]);
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
List[i][j]=j;
for(k=1;k<=n;k++)
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
if(a[k][List[k][i]]>a[k][List[k][j]]){
int tmp=List[k][i];
List[k][i]=List[k][j];
List[k][j]=tmp;
}
for(i=2;i<=n;i++)
mins=min(mins,a[i][1]);
p[1]=1;
dfs(1,0,1);
printf("%d",ans);
return 0;
}
```
by as2393125 @ 2017-08-10 20:21:01