light oj 1011 - Marriage Ceremonies (状态压缩+记忆化搜索)

题目链接

     大概题意是有n个男的n个女的（原谅我这么说，我是粗人），给你一个n*n的矩阵，第i行第j列表示第i个女（男）对第j个男（女）的好感度，然后要安排n对相亲，保证都是正常的（无搞基百合之类的），然后求怎么安排能使好感度和最大，求出最大值。

    开始试了纯暴力的方法，时间复杂度是n！果断超时

  

   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     

      #include <string.h>
     
    
   

    

     

    
    

     

      #include <algorithm>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int vis[17];
     
    
   

    

     

    
    

     

      int n, ans, sum;
     
    
   

    

     

    
    

     

      int map[19][19];
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void dfs(int x)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    if (x == n+1)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              ans = max(ans, sum);
     
    
   

    

     

    
    

     
        return;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    for (int i = 1; i <= n; i++)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        if (vis[i] == 0)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

                  sum += map[x][i];
     
    
   

    

     

    
    

     

                  vis[i] = 1;
     
    
   

    

     

    
    

     
            dfs(x+1);
     
    
   

    

     

    
    

     

                  vis[i] = 0;
     
    
   

    

     

    
    

     

                  sum -= map[x][i];
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    int t;
     
    
   

    

     

    
    

     

          cin >> t;
     
    
   

    

     

    
    

     
    for (int kase = 1; kase <= t; kase++)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              cin >> n;
     
    
   

    

     

    
    

     
        for (int i = 1; i <= n; i++)
     
    
   

    

     

    
    

     
            for (int j = 1; j <= n; j++)
     
    
   

    

     

    
    

     

                      cin >> map[i][j];
     
    
   

    

     

    
    

     

              sum = 0;
     
    
   

    

     

    
    

     

              ans = 0;
     
    
   

    

     

    
    

     
        memset(vis, 0, sizeof(vis));
     
    
   

    

     

    
    

     
        dfs(1);
     
    
   

    

     

    
    

     

              cout << "Case " << kase << ": " << ans << endl;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

  

   

    

     

    
    

     

      //2013-06-25-22.05
     
    
   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     

      #include <string.h>
     
    
   

    

     

    
    

     

      #include <algorithm>
     
    
   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      const int maxn = 1<<16;
     
    
   

    

     

    
    

     

      int vis[17];
     
    
   

    

     

    
    

     

      int n, ans, sum;
     
    
   

    

     

    
    

     

      int map[19][19];
     
    
   

    

     

    
    

     

      int dp[maxn];
     
    
   

    

     

    
    

     

      int dfs(int x, int d)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    if (x == 0)
     
    
   

    

     

    
    

     
        return 0;
     
    
   

    

     

    
    

     
    if (dp[x])
     
    
   

    

     

    
    

     
        return dp[x];
     
    
   

    

     

    
    

     
    for (int i = 0; i < n; i++)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        if (x&(1<<i))
     
    
   

    

     

    
    

     

                  dp[x] = max(dfs(x^(1<<i), d-1)+map[i+1][d], dp[x]);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    return dp[x];
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    int t;
     
    
   

    

     

    
    

     

          cin >> t;
     
    
   

    

     

    
    

     
    for (int kase = 1; kase <= t; kase++)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              cin >> n;
     
    
   

    

     

    
    

     
        for (int i = 1; i <= n; i++)
     
    
   

    

     

    
    

     
            for (int j = 1; j <= n; j++)
     
    
   

    

     

    
    

     

                      cin >> map[i][j];
     
    
   

    

     

    
    

     
        memset(dp, 0, sizeof(dp));
     
    
   

    

     

    
    

     

              ans = dfs((1<<n)-1, n);
     
    
   

    

     

    
    

     
        printf("Case %d: %d\n", kase, ans);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: xindoo.blog.csdn.net，作者：xindoo，版权归原作者所有，如需转载，请联系作者。

原文链接：xindoo.blog.csdn.net/article/details/9173949