光光住在農(nóng)村，離他的家不遠(yuǎn)有一口井，傳說是光光的祖先開掘的。雖然光光的村子里通了自來水，但是由于這口井井水質(zhì)量非常的好，因此光光仍然喝這口井里的水。光光非常喜歡這口井，所以他經(jīng)常去打水。

光光的家里有 n（n 是偶數(shù)且n<=18）只桶，這些桶雖然大小相等，但是由于很多都有些破損，所以認(rèn)為它們是不同的。光光經(jīng)常挑一根扁擔(dān)（帶兩只空桶，必須是空的，且是2 只）去井邊打水。光光每次去井旁都會(huì)把桶中的水裝到極限（假設(shè)水量無窮，且光光都能夠擔(dān)得動(dòng)）。設(shè)光光挑得是x、y 兩只桶，則打水一趟需要走 time[x,y]分鐘。光光想要在最少的時(shí)間內(nèi)用自己的力量把家里所有的空桶裝滿。光光覺得這是個(gè)難題，于是來找你幫忙。

這道題并不是一道難題，只不過要注意搜索的對(duì)象。一開始的時(shí)候，我的做法是依次枚舉第1、2、……、n/2次選取的情況，這樣做的結(jié)果是只能通過4組數(shù)據(jù)。后來改變了搜索對(duì)象，依次枚舉第1、2、……、n個(gè)水桶和哪個(gè)水桶相匹配。這樣的話全部數(shù)據(jù)加在一起用時(shí)不到0.2s（請(qǐng)自行思考為什么這么做可行）。

以下是我的代碼：

#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;
}