LightOJ 1011 Marriage Ceremonies (二分图最优匹配状态压缩+记忆化搜索)

一时失言乱红尘 2022-09-18 04:00 113阅读 0赞

题目链接：http://lightoj.com/volume\_showproblem.php?problem=1011

题意：n男n女要结婚，给出好感度矩阵，i行j列表示i男对j女的好感度，求一夫一妻结婚后总的最大好感度。

思路：套了个KM算法的模板0.004s直接秒了……然后觉得可以用状态压缩+记忆化搜索来练练手，结果跑了0.256s。。。

网上貌似还有用费用流做的。

#include <cstdio>
    #include <cstring>
    #define max(a,b) ((a)>(b)?(a):(b))
    
    const int maxn = 1<<16;
    const int N=20;
    
    int data[N][N];
    int n;
    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)+data[i+1][d],dp[x]);
        return dp[x];
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int T;
    	scanf("%d",&T);
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    	    scanf("%d",&n);
    	    memset(dp,0,sizeof(dp));
    	    for (int i=1;i<=n;i++)
                for (int j=1;j<=n;j++)
                    scanf("%d",&data[i][j]);
            printf("Case %d: %d\n",Cas,DFS((1<<n)-1,n));
        }
        return 0;
    }

#include <cstdio>
    #include <cstring>
    #include <cmath>
    
    const int N=20;   //每个集合的最大点数
    const int INF=0x3f3f3f3f;
    
    template<typename Type>
    class KM_Matrix    //KM算法,邻接矩阵
    {//求最大匹配边的总长及相应匹配。若求最小,加边时加负值
    private:
    	int nx,ny;  //nx,ny分别为x点集y点集的个数
    	int link[N];   //link[a]=b代表 y集合中的a与x集合中的b匹配
    	Type slack[N];    //优化
    	bool visx[N],visy[N];
    	Type lx[N],ly[N],w[N][N];    //lx,ly为顶标,w[][]记录各边权值
    
    	bool DFS (int x)
    	{
    		visx[x]=true;
    		for (int y=1;y<=ny;y++)
    		{
    			if (visy[y])
    				continue;
    			Type t = lx[x] + ly[y] - w[x][y];
    			if (t==0)
    //			if (fabs(t)<1e-10)     //注意精度
    			{
    				visy[y]=true;
    				if (link[y] == -1 || DFS(link[y]))
    				{
    					link[y] = x;
    					return true;
    				}
    			}
    			else if (slack[y] > t)  //不在相等子图中slack 取最小的
    				slack[y] = t;
    		}
    		return false;
    	}
    	
    public:
    
    	void Init (int _nx,int _ny)
    	{
    		nx=_nx;
    		ny=_ny;
    		memset (link,-1,sizeof(link));
    		memset (ly,0,sizeof(ly));
    		for (int i=0;i<=nx;i++)       //初始化,注意修改
    			for (int j=0;j<=ny;j++)
    				w[i][j]=INF;
    	}
    
    	void Add (int u,int v,Type val)  //加边
    	{
    		w[u][v]=val;
    	}
    
    	Type KM ()
    	{
    		int i,j;
    		for (i=1;i<=nx;i++)      //lx初始化为与它关联边中最大的
    			for (j=1,lx[i]=-INF;j<=ny;j++)
    				if (w[i][j] > lx[i])
    					lx[i] = w[i][j];
    		for (int x=1;x<=nx;x++)
    		{
    			for (i=1;i<=ny;i++)
    				slack[i] = INF;
    			while (true)
    			{
    				memset (visx,false,sizeof(visx));
    				memset (visy,false,sizeof(visy));
    				if (DFS(x))     //若成功（找到了增广轨），则该点增广完成，进入下一个点的增广
    					break;  //若失败（没有找到增广轨），则需要改变一些点的标号，使得图中可行边的数量增加。
                   //方法为：将所有在增广轨中（就是在增广过程中遍历到）的X方点的标号全部减去一个常数d，
                   //所有在增广轨中的Y方点的标号全部加上一个常数d
    				Type d = INF;
    				for (i=1;i<=ny;i++)
    					if (visy[i]==false && d>slack[i])
    						d = slack[i];
    				for (i=1;i<=nx;i++) 
    					if (visx[i])
    						lx[i] -= d;
    				for (i=1;i<=ny;i++)//修改顶标后，要把所有不在交错树中的Y顶点的slack值都减去d
    					if (visy[i])
    						ly[i] += d;
    					else
    						slack[i] -= d;
    			}
    		}
    		Type res=0;
    		for (i=1;i<=ny;i++)   //返回总长
    			if (link[i] > -1)
    				res += w[link[i]][i];
    		return res;
    	}
    
    	void Output ()   //按照x集合的顺序输出匹配边的长度
    	{
    		for(int i=1;i<=nx;i++)  
    			for(int j=1;j<=ny;j++)  
    				if (link[j]==i)  
    				{
    					printf("%d\n",j);  
    					break;  
    				}  
    	}
    
    };
    
    KM_Matrix<int> ob;
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int T,n;
    	scanf("%d",&T);
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    		scanf("%d",&n);
    		ob.Init(n,n);
    		int i,j,t;
    		for (i=1;i<=n;i++)
    			for (j=1;j<=n;j++)
    			{
    				scanf("%d",&t);
    				ob.Add(i,j,t);
    			}
            printf ("Case %d: %d\n",Cas,ob.KM());
    	}
    	return 0;
    }
    
    /*
    In:
    4
    2
    96 19
    97 59
    4
    2 52 42 72
    66 58 6 83
    73 83 69 97
    28 81 54 40
    5
    10 46 61 32 39
    98 84 67 4 5
    32 77 49 83 11
    77 53 8 64 23
    15 61 24 14 96
    6
    60 13 46 93 76 98
    33 77 57 35 83 21
    11 50 88 1 87 61
    54 78 73 4 39 90
    47 51 5 1 92 60
    34 3 24 31 47 52
    
    Out:
    Case 1: 155
    Case 2: 288
    Case 3: 401
    Case 4: 474
    */