struct hungary{
int n,m; //X集和Y集的点数
int match[M]; //匹配
bool vis[M]; //是否在增广路上
vector<int>g[M]; //邻接表
void init(int _n,int _m){
n=_n,m=_m,clr(match,-1,m);
for(int i=0;i<n;i++) g[i].clear();
}
void insert(int u,int v){g[u].push_back(v);}
bool augment(int u){//增广
for(int i=0,v;i<g[u].size();i++){
if(!vis[v=g[u][i]]){
vis[v]=1;
if(match[v]==-1 || augment(match[v])){
match[v]=u;
return true;
}
}
}
return false;
}
int maxMatch(){
int res=0;
for(int i=0;i<n;i++){
clr(vis,0,m);
if(augment(i)) res++;
}
return res;
}
};
struct KM{//邻接表
typedef int type;
struct edge{
int from,to;
type w;
edge(int u,int v,type _w){from=u,to=v,w=_w;}
};
int n,m; // X/Y集的点数
int match[M]; // 匹配
type lx[M],ly[M],d; // X/Y项标,松弛量
bool vx[M],vy[M]; // X/Y集的点是否在已经访问
vector<edge>edg; // 边表
vector<int>g[M]; // 邻接表
void init(int _n,int _m){
n=_n,m=_m;
clr(match,-1,m),edg.clear();
for(int i=0;i<n;i++) g[i].clear();
}
void insert(int u,int v,type w){
edg.push_back(edge(u,v,w));
g[u].push_back(edg.size()-1);
}
bool augment(int u){// 增广
vx[u]=1;
for(int i=0;i<g[u].size();i++){
edge& e=edg[g[u][i]];
if(vy[e.to]) continue;
if(lx[u]+ly[e.to]==e.w){
vy[e.to]=1;
if(match[e.to]==-1 || augment(match[e.to])){
match[e.to]=u;
return true;
}
}else getmin(d,lx[u]+ly[e.to]-e.w);
}
return false;
}
type maxWeight(){
int i,j;
for(i=0;i<m;i++) ly[i]=0;
for(i=0;i<n;i++){
lx[i]=-INF;
for(j=0;j<g[i].size();j++)
getmax(lx[i],edg[g[i][j]].w);
}
for(i=0;i<n;i++){
for(;;){
clr(vx,0,n),clr(vy,0,m);
d=-1;
if(augment(i)) break;
for(j=0;j<n;j++) if(vx[j]) lx[j]-=d;
for(j=0;j<m;j++) if(vy[j]) ly[j]+=d;
}
}
type res=0;
for(i=0;i<n;i++) res+=lx[i];
for(i=0;i<m;i++) res+=ly[i];
return res;
}
};
struct KM{//邻接矩阵
typedef int type;
int n,m,match[M]; // X/Y集的点数,匹配
type lx[M],ly[M],w[M][M],d;// X/Y项标,松弛量
bool vx[M],vy[M]; // X/Y集的点是否在已经访问
void init(int _n,int _m){
n=_n,m=_m,clr(match,-1,m);
for(int i=0;i<n;i++) for(int j=0;j<m;j++) w[i][j]=-INF;
}
bool augment(int u){//增广
vx[u]=1;
for(int v=0;v<m;v++){
if(vy[v]) continue;
if(lx[u]+ly[v]==w[u][v]){
vy[v]=1;
if(match[v]==-1 || augment(match[v])){
match[v]=u;
return true;
}
}else getmin(d,lx[u]+ly[v]-w[u][v]);
}
return false;
}
type maxWeight(){
int i,j;
for(i=0;i<m;i++) ly[i]=0;
for(i=0;i<n;i++){
lx[i]=-INF;
for(j=0;j<m;j++)
getmax(lx[i],w[i][j]);
}
for(i=0;i<n;i++){
for(;;){
clr(vx,0,n),clr(vy,0,m);
d=-1;
if(augment(i)) break;
for(j=0;j<n;j++) if(vx[j]) lx[j]-=d;
for(j=0;j<m;j++) if(vy[j]) ly[j]+=d;
}
}
type res=0;
for(i=0;i<n;i++) res+=lx[i];
for(i=0;i<m;i++) res+=ly[i];
return res;
}
};
分享到:
相关推荐
二分图最大匹配(hungary邻接表形式,邻接阵接口) 二分图最大匹配(hungary正向表形式) 二分图最佳匹配(kuhn_munkras邻接阵形式) 一般图最大匹配(邻接表形式) 一般图最大匹配(邻接阵形式) 一般图最大匹配(正向表...
二分图最大匹配(hungary邻接表形式,邻接阵接口) 二分图最大匹配(hungary正向表形式) 二分图最佳匹配(kuhn_munkras邻接阵形式) 一般图最大匹配(邻接表形式) 一般图最大匹配(邻接阵形式) 一般图最大匹配(正向表...
二分图最大匹配(hungary邻接表形式,邻接阵接口) 二分图最大匹配(hungary正向表形式) 二分图最佳匹配(kuhn_munkras邻接阵形式) 一般图最大匹配(邻接表形式) 一般图最大匹配(邻接阵形式) 一般图最大匹配(正向表...
1. 二分图最大匹配(hungary邻接表形式) 2. 二分图最大匹配(hungary邻接表形式,邻接阵接口) 3. 二分图最大匹配(hungary邻接阵形式) 4. 二分图最大匹配(hungary正向表形式) 5. 二分图最佳匹配(kuhn_munkras邻接阵...
1. 二分图最大匹配(hungary邻接表形式) 9 2. 二分图最大匹配(hungary邻接表形式,邻接阵接口) 10 3. 二分图最大匹配(hungary邻接阵形式) 10 4. 二分图最大匹配(hungary正向表形式) 11 5. 二分图最佳匹配(kuhn_munkras...
1. 二分图最大匹配(hungary邻接表形式) 9 2. 二分图最大匹配(hungary邻接表形式,邻接阵接口) 10 3. 二分图最大匹配(hungary邻接阵形式) 10 4. 二分图最大匹配(hungary正向表形式) 11 5. 二分图最佳匹配(kuhn_...
1. 二分图最大匹配(hungary邻接表形式) 9 2. 二分图最大匹配(hungary邻接表形式,邻接阵接口) 10 3. 二分图最大匹配(hungary邻接阵形式) 10 4. 二分图最大匹配(hungary正向表形式) 11 5. 二分图最佳匹配(kuhn_munkras...
“匈牙利算法”可以用于求解多种形式的指派 问题,其基本思想是寻找独立1元素组,而独立1 元素组与图论中对集是一个等价概念,所以与图论中求解赋权二分图最优对集、最大对集的思想是一脉相承的。
8.1 二分图最大匹配(hungary邻接表) 83 8.2 二分图最大匹配(hungary邻接阵) 84 8.3 二分图最大匹配(hungary正向表) 84 8.4二分图最佳匹配(kuhn_munkras邻接阵) 85 8.5 一般图匹配(邻接表) 86 8.6 一般图匹配(邻接阵)...
8.1 二分图最大匹配(hungary邻接表) 83 8.2 二分图最大匹配(hungary邻接阵) 84 8.3 二分图最大匹配(hungary正向表) 84 8.4二分图最佳匹配(kuhn_munkras邻接阵) 85 8.5 一般图匹配(邻接表) 86 8.6 一般图匹配(邻接阵)...
1. 二分图最大匹配(hungary邻接表形式) 9 2. 二分图最大匹配(hungary邻接表形式,邻接阵接口) 10 3. 二分图最大匹配(hungary邻接阵形式) 10 4. 二分图最大匹配(hungary正向表形式) 11 5. 二分图最佳匹配(kuhn_munkras...
1. 二分图最大匹配(hungary 邻接表形式) ..... 9 2. 二分图最大匹配(hungary 邻接表形式,邻接阵接口) ...... 10 3. 二分图最大匹配(hungary 邻接阵形式) ... 10 4. 二分图最大匹配(hungary 正向表形式) ... 11 5. ...
二分图匹配实例代码及整理 1、匈牙利算法 HDU 1150 #include #include #include using namespace std; int m,n,k; int vis[105]; int mpt[105][105]; int use[105]; int hungary(int x) { for(int i=1;i<m;i++)...
hungary_代码_matlab_匈牙利算法_指派问题_源码
说明: 匈牙利算法的matlab实现,自己处理的,克服了大部分的死循环问题 (Hungary matlab solve death circle)
ACM的板子库 嗯,算是总结了一些比较常用的板子吧。 目录 Berlekamp-Massey.cpp:BM算法求递推式 DSU.cpp:按秩合并+路径...Hungary.cpp:匈牙利算法求二分图最大匹配 MincoStFlow.cpp:目前市面比较常用的费用流板子
程序实现了匈牙利算法应用于指派问题,输入指派成本矩阵C,给出最小成本及使得成本最小的最优指派
-匈牙利-水痘-病例 匈牙利每周水痘病例的时空数据集。 该数据集由一个县级邻接矩阵和2005年至2015年之间的县级报告病例的时间序列组成。
讲中国邮路问题的资料,有兴趣的人可以了解了解。