1.最大流
最基本的Ford-Fulkerson算法：每次迭代中 找出任意增广路径p，并把沿p每条边的流f加上其残留容量
EK算法：用广度优先来查找增广路径
#include<queue> #include<iostream> using namespace std; const int maxn = 1000; const int INF = INT_MAX; queue<int>q; int map[maxn][maxn],path[maxn],flow[maxn]; int n,np,nc,m,s,e; int bfs() { while(!q.empty())q.pop(); memset(path,-1,sizeof(path)); memset(flow,0,sizeof(flow)); path[s]=1; flow[s]=INF; q.push(s); while(!q.empty()) { int k=q.front(); q.pop(); if(k==e)break; for(int i=0;i<=n;i++) { if(i!=s&&path[i]==-1&&map[k][i]) { flow[i]=flow[k]<map[k][i]?flow[k]:map[k][i]; path[i]=k; q.push(i); } } } if(path[e]==-1)return -1; else return flow[n]; } int EK() { int max_flow=0,step,now,pre; while((step=bfs())!=-1) { max_flow+=step; now=e; while(now!=s) { pre=path[now]; map[now][pre]+=step; map[pre][now]-=step; now=pre; } /* for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cout<<map[i][j]<<" "; } cout<<endl; } cout<<endl;*/ } return max_flow; }
2.二分图
最大匹配 最小覆盖 都是一样的类型
匈牙利算法：思路一样 每次都寻找增广轨，然后加入
#include <iostream> using namespace std; const int N=510; int map[N][N]; int mark[N]; int father[N]; int n, k; bool dfs(int a) { for(int i=1; i<=n ; i++) { if(map[a][i]&&!mark[i]) { mark[i]=1; if(father[i]==0||dfs(father[i])) { father[i]=a; return true ; } } } return false ; } int hungary() { int ret=0; memset(father , 0 , sizeof(father)); for(int i=1; i<=n; i++) { memset(mark, 0, sizeof(mark)); if(dfs(i)) ret++; } return ret; }
3.KM
用来求最大（最小）匹配
加上一个顶标之后转化成求完备匹配的算法
#include<iostream> #include<cmath> using namespace std; int n, m; char input[200][200]; int map[200][200]; struct node { int x, y; }; node house[10000], men[10000]; int hnum, mennum; const int INF = INT_MAX; int match[200]; int sx[200],sy[200],lx[200],ly[200]; int dfs(int a) { sx[a]=1; for(int i=0;i<hnum;i++) { if(sy[i]==0 && lx[a]+ly[i]==map[a][i]) { sy[i]=1; if(match[i]==-1 || dfs(match[i])==1) { match[i]=a; return 1; } } } return 0; } int km(bool truth)//可以不用更改地处理最小或最大权匹配 { int i,j; if(!truth) { for(i=0;i<hnum;i++) for(j=0;j<hnum;j++) map[i][j]=-map[i][j]; } for(i=0;i<hnum;i++) { lx[i]=-INF; ly[i]=0; for(j=0;j<hnum;j++) if(lx[i]<map[i][j]) lx[i]=map[i][j]; } memset(match,-1,sizeof(match)); for(int u=0;u<hnum;u++) { while(1) { memset(sx,0,sizeof(sx)); memset(sy,0,sizeof(sy)); if(dfs(u)) break; int dmin=INF; for(i=0;i<hnum;i++) { if(sx[i]) { for(j=0;j<hnum;j++) { if(!sy[j]) dmin=(lx[i]+ly[j]-map[i][j])<dmin?(lx[i]+ly[j]-map[i][j]):dmin; } } } for(i=0;i<hnum;i++) { if(sx[i]) lx[i]-=dmin; if(sy[i]) ly[i]+=dmin; } } } int sum=0; for(j=0;j<hnum;j++) sum+=map[match[j]][j]; if(!truth) { sum=-sum; for(i=0;i<hnum;i++) for(j=0;j<hnum;j++) map[i][j]=-map[i][j]; } return sum; }
转载于:https://www.cnblogs.com/w0w0/archive/2012/06/12/2545849.html
