文章目录
匈牙利算法Kuhn_Munkres
最大匹配：二分图中边集的数目最大的那个匹配；
最小顶点覆盖：用最少的点，让每条边都至少和其中一个点关联；
最小边覆盖：用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点；
最大独立集：在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边的点中，m的最大值。
匈牙利算法
class Hungary {
public:
static const int MAXN
= 1e5+100;
static const int MAXM
= 2e5+10;
struct EDGE
{
int v
, to
;
}e
[MAXM
];
int head
[MAXM
], cnt
= 0;
inline void add
( int u
, int v
) {
e
[cnt
].v
= v
, e
[cnt
].to
= head
[u
]; head
[u
] = cnt
++;
}
int n
, ans
;
int link
[MAXN
];
bool use
[MAXN
];
Hungary
( ) { };
Hungary
( int _n
) : n(_n
) { };
void ini
( int n
) {
this->n
= n
;
cnt
= 0; memset( head
, -1, sizeof(head
) );
}
private:
bool dfs
( int u
) {
for ( int k
= head
[u
]; k
!= -1; k
= e
[k
].to
) {
int v
= e
[k
].v
;
if ( use
[v
] ) continue;
use
[v
] = true;
if ( link
[v
] == -1 || dfs
( link
[v
] ) ) {
link
[v
] = u
;
return true;
}
}
return false;
}
public:
int run
( ) {
ans
= 0;
memset
( link
, 255, sizeof ( link
) );
for ( int i
= 0; i
< n
; ++i
) {
memset
( use
, 0, sizeof ( use
) );
if ( dfs
( i
) )
++ans
;
}
return ans
;
}
}h
;
Kuhn_Munkres
class Kuhn_Munkres {
public:
static const int MAXN
= 310;
static const int INF
= 0x3f3f3f3f;
int n
;
int graph
[MAXN
][MAXN
];
bool visx
[MAXN
], visy
[MAXN
];
int lx
[MAXN
], ly
[MAXN
], match
[MAXN
], slack
[MAXN
];
Kuhn_Munkres
( ) { };
Kuhn_Munkres
( int _n
) : n(_n
) { };
inline void add
( int u
, int v
, int w
) {
graph
[u
][v
] = w
;
}
inline void ini
( int n
) {
this->n
= n
;
memset( graph
, 0, sizeof(graph
) );
}
bool dfs
( int x
) {
visx
[x
] = true;
for ( int i
= 1; i
<= n
; i
++ ) {
if ( visy
[i
] )
continue;
int temp
= lx
[x
] + ly
[i
] - graph
[x
][i
];
if ( temp
== 0 ) {
visy
[i
] = true;
if ( match
[i
] == -1 || dfs
( match
[i
] ) ) {
match
[i
] = x
;
return true;
}
}
else if ( slack
[i
] > temp
)
slack
[i
] = temp
;
}
return false;
}
long long run
( ) {
memset
( match
, -1, sizeof ( match
) );
memset
( ly
, 0, sizeof ( ly
) );
int i
, j
, k
;
for ( i
= 1; i
<= n
; i
++ )
for ( j
= 1, lx
[i
] = -INF
; j
<= n
; j
++ )
if ( graph
[i
][j
] > lx
[i
] )
lx
[i
] = graph
[i
][j
];
for ( i
= 1; i
<= n
; i
++ ) {
memset
( slack
, 0x3f, sizeof ( slack
) );
while ( 1 ) {
memset
( visx
, 0, sizeof ( visx
) );
memset
( visy
, 0, sizeof ( visy
) );
if ( dfs
( i
) )
break;
int temp
= INF
;
for ( k
= 1; k
<= n
; k
++ )
if ( !visy
[k
] && temp
> slack
[k
] )
temp
= slack
[k
];
for ( j
= 1; j
<= n
; j
++ )
if ( visx
[j
] )
lx
[j
] -= temp
;
for ( int j
= 1; j
<= n
; j
++ )
if ( visy
[j
] )
ly
[j
] += temp
;
else
slack
[j
] -= temp
;
}
}
long long ans
= 0;
for ( int i
= 1; i
<= n
; i
++ )
ans
+= graph
[match
[i
]][i
];
return ans
;
}
}km
;
