图论里有一个非常经典的算法，那就是二分匹配，只是仅仅是简单的匹配有时并不能解决我们的问题，比方匹配带权的情况。引申的一个非常重要的问题就是分配问题，比方给n个人分派m个任务，每一个人都有不同的成本，怎样分配能使得成本最小就是这种问题，这种问题我们统称为二分图的最大权匹配问题.
解决这类问题的最好的方法应该就是KM 算法。详细细节能够自己百度！
以下是我的代码，我主要还是用了类来写，认为这样比較好理解！
#include这个算法的效率是O(n^3)的，这应该是眼下最好的算法了吧。#include #include using namespace std;#define INF 99999999class graph{ struct vertex { bool vist; //是否被訪问过 int link; //顶标 int ver; //匹配边 vector edge; //相关边 vertex(bool f=0,int v=0,int l=-INF):vist(f),ver(v),link(l){} }; int n,m; vector V; vector U; vector 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< <