最大權二分比對

圖論裡有一個很經典的算法，那就是二分比對，不過隻是簡單的比對有時并不能解決我們的問題，比如比對帶權的情況，引申的一個很重要的問題就是配置設定問題，比如給n個人分派m個任務，每個人都有不同的成本，如何配置設定能使得成本最小就是這樣的問題，這樣的問題我們統稱為二分圖的最大權比對問題.

解決這類問題的最好的方法應該就是KM 算法，具體細節可以自己百度！

下面是我的代碼，我主要還是用了類來寫，覺得這樣比較好了解！

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
#define INF 99999999
class graph{
  struct vertex
  {
	 bool vist;              //是否被通路過
     int link;              //頂标
     int ver;               //比對邊
	 vector<int>edge;      //相關邊
	 vertex(bool f=0,int v=0,int l=-INF):vist(f),ver(v),link(l){}
  };
  int n,m;
  vector<vertex>V;
  vector<vertex>U;
  vector<int>slack;
  public:
	  graph(int x,int y):n(x),m(y)
	  {
		  vertex tmp;
		  int i=0;
		  for(;i<=n;i++)
		  V.push_back(tmp),
		  V[i].edge.push_back(0);
		  for(i=0;i<=m;i++)
			  U.push_back(tmp),
			  slack.push_back(INF);
	  }
	  void merge(int i,int w)
	  {
		  V[i].edge.push_back(w);
		  V[i].link=V[i].link>w?V[i].link:w;
	  }
      bool DFS(int x)
	  {
		  V[x].vist=1;
		  for(int y=1;y<=m;y++)
		  {
             if(U[y].vist)
				 continue;
			 int tmp=V[x].link+U[y].link-V[x].edge[y];
			 if(tmp==0)
			 {
				 U[y].vist=1;
				 if(U[y].ver==0||DFS(U[y].ver))
				 {
					 U[y].ver=x;
					 V[x].ver=y;
					 return 1;
				 }
			 }
			 else if(slack[y]>tmp)
				 slack[y]=tmp;
		  }
		  return 0;
	  }
    int KM()
	{
		for(int x=1;x<=n;x++)
		{
		   for(int i=1;i<=m;i++)
		    slack[i]=INF;
         while(1)
		 {
		   for(int i=1;i<=n;i++)
		    V[i].vist=0;
		    for(int i=1;i<=m;i++)
		    U[i].vist=0;
		   if(DFS(x))
               break;
             int d=INF ;
            for(int i=1;i<=m;i++)
				if(!U[i].vist&&d>slack[i])
					d=slack[i];
			for(int j=1;j<=n;j++)
				if(V[j].vist)
					V[j].link-=d;
			for(int k=1;k<=m;k++)
				if(U[k].vist)
					U[k].link+=d;
				else
					slack[k]-=d;
		 }
       }
    	int MAX=0;
    	for(int i=1;i<=m;i++)
	    {
	       if(V[i].ver>0)
            MAX+=V[U[i].ver].edge[i];

        }
		return MAX;
	}

  };

int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
	int n,m;
	while(cin>>n>>m)
	{
	  graph G(n,n);
	  int w;
	  for(int i=1;i<=n;i++)
		  for(int j=1;j<=n;j++)
			 scanf("%d",&w),
			 G.merge(i,-w);
	  int max=-G.KM();
          cout<<max<<endl;
	

	}
	  //  fclose(stdin);
	//    fclose(stdout);
	return 0;
}



           

這個算法的效率是O(n^3)的，這應該是目前最好的算法了吧！