二分图匹配匈牙利算法——学习与改进——Bounty Hunter II

34 / 134 B Gym 100753B Bounty Hunter II

来源题解目录
比赛link
这道题我和队长是一起看过的，可是最后没有做出来，当时还讨论了很多情况，没想到最后在网上找到的题解的思路如此简单暴力。

https://blog.csdn.net/weixin_30268071/article/details/96471391
博主思路：在一个有向图中，求最少可以分人一条路径，是的每个路径的顶点都不重复。可以转换成求二分图最大匹配

但是认真看了代码才知道，原来我弄不懂二分图。看到n~2n开始还笑为什么白开一段，是我没文化真可怕了qwq

二分图匹配，匈牙利算法

看懂了的讲解视频
代码实现笔记
题解
给定一张DAG，求一种方案：用最少的路径将所有点覆盖。写了按长度贪心，按出度的贪心。。。果断挂了。下来搜了下题解，看到了二分图。就懂了。。。把点拆开，每个出点最多允许连一个入点，反之也是这样。那不就是二分图最大匹配吗？然后把用到的边加进去，算一下联通的链就行了，然后再考虑一下，既然是一条条链，把他们原先看作一条链，然后再断开，断开的地方加1，就是答案，断开的位置一共就有 (点数-边数) 个，那就解决了。

6
0
1 2
2 4 5
1 2
0
0
结果：4

我改进了一下存储：
//这是记录起点有没有被连 ，>=n的部分是记录终点。节省空间可份俩
//但是我发现不需要记录起点有没有被连
原来15.9MB，现在是4MB

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#ifdef LOCAL
FILE*FP=freopen("text.in","r",stdin);
//FILE*fp=freopen("text.out","w",stdout);
#endif
using namespace std;
const int N = 1e3+10;
int edge[N][N], vis[N], match[N];
int n, k, v, u;bool dfs(int v) {
    for(int i = 0; i < n; i ++) {
    //看看所有点是否有路 if(edge[v][i] && !vis[i]) {
    //vis标记访问到的点 ,针对于一个出发点 vis[i] = 1;if(match[i] == -1 || dfs(match[i])) {
    //1.还没连,就连起来2.已经有连的，就看看来源可不可以换一换 match[i] = v;return true;}}}return false;
}
int max_match() {
    int res = 0;memset(match, -1, sizeof(match));//记录匹配 for(int i = 0; i < n; i ++) {
    //这是记录起点有没有被连 ，>=n的部分是记录终点。节省空间可份俩 //但是我发现不需要记录起点有没有被连 memset(vis, 0, sizeof(vis));//dfs不重复用 if(dfs(i)) res++;//找的到线牵，同时不减少已有的线 }return res;
}
int main() {
    cin >> n;for(int i = 0; i < n; i ++) {
    cin >> k;for(int j = 0; j < k; j ++) {
    cin >> v;edge[i][v] = 1;//第i个点到第v号 }}cout << n-max_match() << endl;//注意n-return 0;
}

6
0
1 2
2 4 5
2 2 4
0 
0结果：3 ......正确（我以为错了）

改进：
我想现在每次都要看每一条判断是不是有路
为什么不只存路，像Dijkstra算法一样星式存图呢
可以快很多

成了！
对比，上面是811ms，下面只要171ms
巨爽

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
//#include<iostream>
//#include<algorithm>
//#include<string>
//#include<sstream>
//#include<vector>
//#include<map>
//#include<set>
//#include<ctype.h>
//#include<stack>
//#include<queue>
#ifdef LOCAL
FILE*FP=freopen("text.in","r",stdin);
//FILE*fp=freopen("text.out","w",stdout);
#endif
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define _forplus(i,a,b) for( register int i=(a); i<=(b); i++)
#define _forsub(i,a,b) for( register int i=(a); i>=(b); i--)
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
#define INF 0x3f3f3f3f
#define pi (acos(-1))
const int N=(1e3+10);
int e[N][N]={
    -1},vis[N],match[N]; //语法：match[N]={-1}只能第一个-1,c语言基础啊 
int n,t,cnt;
bool dfs(int now){
    _forplus(i,1,e[now][0]){
    if(vis[e[now][i]])continue;vis[e[now][i]]=1;if(match[e[now][i]]==-1||dfs(match[e[now][i]])){
    match[e[now][i]]=now;return true;}}return false;
}
int max_match(){
    int res=0;mem(match,-1);_forplus(i,0,n-1){
    mem(vis,0);if(dfs(i))res++;}return res;
}
int main(){
    scanf("%d",&n);_forplus(i,0,n-1){
    scanf("%d",&e[i][0]);_forplus(j,1,e[i][0]){
    scanf("%d",&t);e[i][j]=t;}}printf("%d\n",n-max_match());return 0;
}