二分图最佳匹配 KM算法 Hdu2255奔小康赚大钱 + Poj 3565 Ants

墨蓝 2021-11-22 20:34 278阅读 0赞

2014-10-4 更新 在最下面增加了基于邻接表的模板

理论：http://blog.sina.com.cn/s/blog\_691ce2b701016reh.html

http://philoscience.iteye.com/blog/1754498

写模板的时候参考了上面两篇博文中的写法。

**Hdu 2255** **奔小康赚大钱**

#include <cstdio>
    #include <cstring>
    #include <cmath>
    
    const int N=310;   //每个集合的最大点数
    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 ()
    {
    	int n;
    	while (~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 ("%d\n",ob.KM());
    	}
    	return 0;
    }

**Poj 3565 Ants**

思路参考：http://www.cnblogs.com/Missa/archive/2012/09/29/2708604.html

#include <cstdio>
    #include <cstring>
    #include <cmath>
    
    const int N=105;   //每个集合的最大点数
    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 (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<double> ob;
    
    struct Point
    {
    	double x,y;
    	void Get ()
    	{
    		scanf("%lf%lf",&x,&y);
    	}
    	double Dis (const Point& b) const
    	{
    		return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y));
    	}
    }a[N],b[N];
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int n;
    	while (~scanf("%d",&n))
    	{
    		ob.Init(n,n);
    		int i;
    		for (i=1;i<=n;i++)
    			a[i].Get();
    		for (i=1;i<=n;i++)
    			b[i].Get();
    		for (i=1;i<=n;i++)
    			for (int j=1;j<=n;j++)
    			{
    				double len=a[i].Dis(b[j]);
    				ob.Add(i,j,-len);
    			}
    		ob.KM();
    		ob.Output();
    		printf("\n");
    	}
    	return 0;
    }

基于邻接表的模板，转自 http://paste.ubuntu.com/8489918/

/*
    * this code is made by hdu_sxz
    * Problem: 1223
    * Verdict: Accepted
    * Submission Date: 2014-10-03 20:49:11
    * Time: 8MS
    * Memory: 18316KB
    */
    #pragma comment(linker,"/STACK:102400000,102400000")
    #include <iostream>
    #include <string.h>
    #include <stdio.h>
    #include <algorithm>
    #include <vector>
    #include <string>
    #include <math.h>
    #include <queue>
    #include <stack>
    #include <map>
    #include <set>
    using namespace std;
    typedef long long ll;
    const int maxn=505;
    const int maxm=1000005;
    const int INF=1000000000;
    struct EdgeNode{int from,to,id,next;}edge[maxm];
    int head[maxn],cnt,cost[maxn],vis[maxn];
    void add(int x,int y,int id)
    {
        edge[cnt].from=x;
        edge[cnt].to=y;
        edge[cnt].id=id;
        edge[cnt].next=head[x];
        head[x]=cnt++;
    }
    void init()
    {
        cnt=0;
        memset(head,-1,sizeof(head));
    }
    int n,nx,ny,m;
    int march[maxn],lx[maxn],ly[maxn],slack[maxn];
    int visx[maxn],visy[maxn],w[maxn][maxn];
     
    int dfs(int x)
    {
        visx[x]=1;
        for(int y=1;y<=ny;y++)
        {
            if(visy[y])
                continue;
            int t=lx[x]+ly[y]-w[x][y];
            if(t==0)
            {
                visy[y]=1;
                if(march[y]==-1||dfs(march[y]))
                {
                    march[y]=x;
                    return 1;
                }
            }
            else if(slack[y]>t)
                slack[y]=t;
        }
        return 0;
    }
     
    int KM()
    {
        int i,j;
        memset(march,-1,sizeof(march));
        memset(ly,0,sizeof(ly));
        for(i=1;i<=nx;i++)
            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(1)
            {
                memset(visx,0,sizeof(visx));
                memset(visy,0,sizeof(visy));
                if(dfs(x))break;
                int d=INF;
                for(i=1;i<=ny;i++)
                    if(!visy[i]&&d>slack[i])
                        d=slack[i];
                for(i=1;i<=nx;i++)
                    if(visx[i])
                        lx[i]-=d;
                for(i=1;i<=ny;i++)
                    if(visy[i])
                        ly[i]+=d;
                    else
                        slack[i]-=d;
            }
        }
        int res=0;
        for(i=1;i<=ny;i++)
            if(march[i]>-1)
                res+=w[march[i]][i];
        return res;
    }
     
    bool find(int x,int y,int id)
    {
        if(x==y)return 1;
        vis[x]=1;
        for(int i=head[x];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if(vis[v])continue;
            if(find(v,y,id)){
                if(cost[edge[i].id]>cost[id])
                   w[edge[i].id][id]=cost[edge[i].id]-cost[id];
                return 1;
            }
        }
        return 0;
    }
     
    int main()
    {
        int x,y,z,id,i;
        while(~scanf("%d%d",&n,&m))
        {
            init();
            for(i=1;i<n;i++){
                scanf("%d%d%d",&x,&y,&cost[i]);
                add(x,y,i);
                add(y,x,i);
            }
            memset(w,0,sizeof(w));
            for(i=n;i<=m;i++){
                scanf("%d%d%d",&x,&y,&cost[i]);
                memset(vis,0,sizeof(vis));
                find(x,y,i);
            }
            nx=n-1; ny=m;
            KM();
            for(i=1;i<n;i++)
            printf("%d\n",cost[i]-lx[i]);
            for(i=n;i<=m;i++)
            printf("%d\n",cost[i]+ly[i]);
        }
        return 0;
    }