光光住在农村，离他的家不远有一口井，传说是光光的祖先开掘的。虽然光光的村子里通了自来水，但是由于这口井井水质量非常的好，因此光光仍然喝这口井里的水。光光非常喜欢这口井，所以他经常去打水。

光光的家里有 n（n 是偶数且n<=18）只桶，这些桶虽然大小相等，但是由于很多都有些破损，所以认为它们是不同的。光光经常挑一根扁担（带两只空桶，必须是空的，且是2 只）去井边打水。光光每次去井旁都会把桶中的水装到极限（假设水量无穷，且光光都能够担得动）。设光光挑得是x、y 两只桶，则打水一趟需要走 time[x,y]分钟。光光想要在最少的时间内用自己的力量把家里所有的空桶装满。光光觉得这是个难题，于是来找你帮忙。

这道题并不是一道难题，只不过要注意搜索的对象。一开始的时候，我的做法是依次枚举第1、2、……、n/2次选取的情况，这样做的结果是只能通过4组数据。后来改变了搜索对象，依次枚举第1、2、……、n个水桶和哪个水桶相匹配。这样的话全部数据加在一起用时不到0.2s（请自行思考为什么这么做可行）。

以下是我的代码：

#include<stdio.h>
#define MAXINT 200000000
long n,ans=MAXINT,a[20][20]={0},used[20]={0};
void dfs(long dep,long now)
{
    long i,j;
    if(dep>n)
    {
       if(now<ans) ans=now;
       return;
    }
    if(used[dep])
    {
       dfs(dep+1,now);
       return;
    }
    used[dep]=1;
    for(i=dep+1;i<=n;i++)
      if(!used[i]&&a[dep][i]!=0&&now+a[dep][i]<ans)
      {
         used[i]=1;
         dfs(dep+1,now+a[dep][i]);
         used[i]=0;
      }
    used[dep]=0;
}
int main()
{
    FILE *fin,*fout;
    long i,j,k,min,t1,t2;
    fin=fopen("spring.in","r");
    fscanf(fin,"%ld",&n);
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
        fscanf(fin,"%ld",&a[i][j]);
    fclose(fin);// Read In
    dfs(1,0);
    fout=fopen("spring.out","w");
    fprintf(fout,"%ld\n",ans);
    fclose(fout);
return 0;
}