Znzryb's Blog
0%

Posted on Edited on

shift+command+/ 表示/。。。/

Posted on Edited on

题目大意

给定一个二分图，左部点集大小 n，右部点集大小 m，边集大小 e。求该二分图的最大匹配数（即最多的边数，使得这些边没有任何公共端点）。

AC代码

增广路的神奇之处在于，如果我们沿着一条增广路，将路径上的非匹配边变成匹配边，同时将匹配边变成非匹配边，那么匹配边的总数就会增加 1。

举个例子：

假设我们有下面这条增广路（实线代表匹配边，虚线代表非匹配边）：

增广路的定义是一条从未匹配点出发，依次交替经过“非匹配边”和“匹配边”，最终到达另一个未匹配点的路径。

未匹配点1 --(虚线)--> 点A ==(实线)== 点B --(虚线)--> 未匹配点2

  • 这条路径从一个未匹配点开始，到一个未匹配点结束。

  • 路径上的边是“非匹配-匹配-非匹配”交替的。

如果我们对它进行“增广”操作（虚实互换）：

未匹配点1 ==(实线)== 点A --(虚线)-- 点B ==(实线)== 未匹配点2

看！原来的 1 条匹配边（A-B）现在变成了 2 条（点1-A，B-点2）。匹配的总数增加了！

一个重要的结论是：一个匹配是最大匹配，当且仅当图中不存在增广路。 这也构成了匈牙利算法的理论基础。

最新算法模板看这个：

2026 杭电春季联赛 2——1002-庭扫落樱（二分图最大匹配）（最小边覆盖和最大匹配之间的关系）

视频教程

https://www.acwing.com/video/290/

匈牙利算法精髓：

👉 Note: 姑娘 j （connectedr）遇到新的追求者的心理活动：如果原来的男朋友有备胎，我就绿他，如果没有，那我看他太可怜了，就一直跟他在一起吧。

还有一个要注意的地方就是vis数组每次都要清空，因为实际上记的是这次寻找有没有找过这个宠物，这是为了防止死循环的发生（爆栈）

AC https://www.luogu.com.cn/record/183163854

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// https://www.luogu.com.cn/problem/P3386
// https://www.acwing.com/problem/content/863/
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll N=510;
ll n,m,u,v,e,ans;
vector<ll> g[N],r[N];
bool vis[N];
ll matchr[N];
bool find(ll i) {
    for(int j=0;j<g[i].size();j++) {
        ll connectedr=g[i][j];
        if(vis[connectedr])
            continue;
        vis[connectedr]=true;
        if(matchr[connectedr]==0 || find(matchr[connectedr]) ) {
            matchr[connectedr]=i;
            return true;
        }
    }
    return false;
}
int main()
{
    cin>>n>>m>>e;
    for(int i=1;i<=e;i++) {
        cin>>u>>v;
        // if(removeSame[u][v])
        //     continue;
        // removeSame[u][v]=true;
        g[u].push_back(v);
    }
    for(int i=1;i<=n;i++) {
        fill(&vis[0],&vis[n+1],false);
        if(find(i))
            ++ans;
    }
    cout<<ans<<endl;
    return 0;
}

// 70 pts https://www.luogu.com.cn/record/183070840
// 80 pts https://www.luogu.com.cn/record/183076675
// AC https://www.luogu.com.cn/record/183163854

心路历程（WA，TLE，MLE……）

好像有点问题，但问题不大，过了70pts

https://www.luogu.com.cn/record/183070840

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// https://www.luogu.com.cn/problem/P3386
// https://www.acwing.com/problem/content/863/
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll N=510;
ll n,m,u,v,e,ans;
vector<ll> l[N],r[N];
bool removeSame[N][N];
ll matchr[N],sl[N];     // sl为左边点的起始索引记录
inline void Hungarian(){    // 匈牙利算法
    for(int i=1;i<=n;i++) {
        if(l[i].empty())
            continue;
        if(matchr[l[i][0]]==0) {
            matchr[l[i][0]]=i;
            ++sl[i];++ans;
        }else {
            ll originMatch=matchr[l[i][0]];bool isBreak=false;
            for(ll j=sl[originMatch];j<l[originMatch].size();j++) {
                ll rConnected=l[originMatch][j];
                if(matchr[rConnected]==0) {
                    matchr[rConnected]=originMatch;
                    sl[originMatch]=j+1;isBreak=true;       // 只是换了一下配对关系，无需++ans
                    break;
                }
            }
            if(isBreak) {
                matchr[l[i][0]]=i;
                ++sl[i];
                ++ans;
            }
        }
    }
}
int main()
{
    cin>>n>>m>>e;
    for(int i=1;i<=e;i++) {
        cin>>u>>v;
        // if(removeSame[u][v])
        //     continue;
        // removeSame[u][v]=true;
        l[u].push_back(v);
        r[v].push_back(u);
    }
    Hungarian();
    cout<<ans<<endl;
    return 0;
}

// 70 pts https://www.luogu.com.cn/record/183070840

80pts https://www.luogu.com.cn/record/183076675

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// https://www.luogu.com.cn/problem/P3386
// https://www.acwing.com/problem/content/863/
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll N=510;
ll n,m,u,v,e,ans;
vector<ll> g[N],r[N];
bool removeSame[N][N];
ll matchr[N],sl[N];     // sl为左边点的起始索引记录
inline void Hungarian(){    // 匈牙利算法
    for(int i=1;i<=n;i++) {
        if(g[i].empty())
            continue;
        if(matchr[g[i][0]]==0) {
            matchr[g[i][0]]=i;
            ++sl[i];++ans;
        }else {
            for(int k=0;k<g[i].size();k++) {
                ll originMatch=matchr[g[i][k]];bool isBreak=false;
                for(ll j=sl[originMatch];j<g[originMatch].size();j++) {
                    ll rConnected=g[originMatch][j];
                    if(matchr[rConnected]==0) {
                        matchr[rConnected]=originMatch;
                        sl[originMatch]=j+1;isBreak=true;       // 只是换了一下配对关系，无需++ans
                        break;
                    }
                }
                if(isBreak) {
                    matchr[g[i][0]]=i;
                    ++sl[i];
                    ++ans;
                    break;
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m>>e;
    for(int i=1;i<=e;i++) {
        cin>>u>>v;
        // if(removeSame[u][v])
        //     continue;
        // removeSame[u][v]=true;
        g[u].push_back(v);
    }
    Hungarian();
    cout<<ans<<endl;
    return 0;
}

// 70 pts https://www.luogu.com.cn/record/183070840
// 80 pts https://www.luogu.com.cn/record/183076675

用循环是解决不了的，还是要递归。

Posted on Edited on

题目大意

给定一个无向图，判断该图是否为二分图（即是否能将所有点分成两个集合，使得所有边都只连接不同集合的点）。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll N=1e5+10;
ll n,m,u,v;
short int color[N];
vector<ll> g[N];
bool isErfen=true;
void dfs(int x,int c) {
    if(isErfen==false)
        return;
    if(color[x]==0)
        color[x]=c;
    else {
        if(color[x]!=c) {
            isErfen=false;
            return;
        }
        return;
    }
    for(int i=0;i<g[x].size();i++) {
        dfs(g[x][i],3-c);       // 小的一个trick
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++) {
        if(color[i]==0)
            dfs(i,1);
        if(isErfen==false)
            break;
    }
    if(isErfen)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}
// AC https://www.acwing.com/problem/content/submission/code_detail/37509674/

Posted on Edited on

题目大意

给定一个有向带权图（NN 点 MM 边），求从源点 ss 到所有其他点的最短路径长度。数据范围较大（Nle105,Mle2times105N le 10^5, M le 2 times 10^5），需要 O(Mlog⁡N)O(M \log N) 级别的算法（如堆优化 Dijkstra）。

AC代码

Compare函数/类的使用

注意，priority_queue的比较操作符与sort，set是反的

参考题解：https://www.luogu.com.cn/problem/solution/P4779

其实总结来讲就是使用堆然后找到dis值最小的点，将其确认为确定点（已经固定了，dis值不太可能再更新了）

https://www.luogu.com.cn/record/181960419

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <vector>
#include <deque>
#include <cmath>
#include <queue>
#define rep(i,n) for(int i=1;i<=(n);i++)
using namespace std;
typedef long long ll;
const ll N=1e5+10,INF=1e18+7;
vector<pair<ll,ll> > g[N];
ll n,m,u,v,w,dis[N],s,vis[N];
struct cmp {
    bool operator () (pair<ll,ll> a,pair<ll,ll> b){
        if(a.second!=b.second)
            return a.second>b.second;
    }
};
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,cmp> heap;
inline void dijkstra() {
    dis[s]=0;
    heap.push(make_pair(s,0));
    while(!heap.empty()) {
        ll cn=heap.top().first,cdis=heap.top().second;  // priority_queue 需要使用.top()访问队首
        heap.pop();
        if(vis[cn])
            continue;
        vis[cn]=true;dis[cn]=cdis;                      // vis 是用来判断是不是已经确定dis的点
        for(int i=0;i<g[cn].size();i++) {
            ll ni=g[cn][i].first; ll wi=g[cn][i].second;
            heap.push(make_pair(ni,cdis+wi));
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>s;
    rep(i,n) {
        dis[i]=INF;
    }
    rep(_,m) {
        cin>>u>>v>>w;
        g[u].push_back(make_pair(v,w));
    }
    dijkstra();
    ll forOut=pow(2,31)-1;
    rep(i,n) {
        if(dis[i]!=INF)
            cout<<dis[i]<<" ";
        else
            cout<<forOut<<" ";
    }
    cout<<endl;
    return 0;
}
//AC https://www.luogu.com.cn/record/181960419

心路历程（WA，TLE，MLE……）

未经堆优化的算法（其实不是Dijkstra）TLE

https://www.luogu.com.cn/record/181877100

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <vector>
#include <deque>
#include <cmath>
#define rep(i,n) for(int i=1;i<=(n);i++)
using namespace std;
typedef long long ll;
const ll N=1e5+10,INF=1e18+7;
vector<pair<ll,ll> > g[N];
ll n,m,u,v,w,dis[N],s;
deque<pair<ll,ll> > q;
void dijkstra() {
    dis[s]=0;
    q.push_back(make_pair(s,0)); // curr_node curr_dis
    while(!q.empty()) {
        ll cn=q.front().first,cdis=q.front().second;
        for(int i=0;i<g[cn].size();i++) {
            ll ni=g[cn][i].first; ll wi=g[cn][i].second;
            if(cdis+wi<dis[ni]) {
                dis[ni]=cdis+wi;
                q.push_back(make_pair(ni,cdis+wi));
            }
        }
        q.pop_front();
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>s;
    rep(i,n) {
        dis[i]=INF;
    }
    rep(_,m) {
        cin>>u>>v>>w;
        g[u].push_back(make_pair(v,w));
    }
    dijkstra();
    ll forOut=pow(2,31)-1;
    rep(i,n) {
        if(dis[i]!=INF)
            cout<<dis[i]<<" ";
        else
            cout<<forOut<<" ";
    }
    cout<<endl;
    return 0;
}
// AC https://www.luogu.com.cn/record/181877100

Posted on Edited on

题目大意

给定一个有向带权图（NN 点 MM 边），求从源点 ss 到所有其他点的最短路径长度。如果无法到达则输出特定值（如 231−12^{31} - 1）。数据范围较小，允许 O(NM)O(NM) 算法。

AC代码

https://www.luogu.com.cn/problem/P3371

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <vector>
#include <deque>
#include <cmath>
#define rep(i,n) for(int i=1;i<=(n);i++)
using namespace std;
typedef long long ll;
const ll N=1e4+10,INF=1e18+7;
vector<pair<ll,ll> > g[N];
ll n,m,u,v,w,dis[N],s;
deque<pair<ll,ll> > q;
void dijkstra() {
    dis[s]=0;
    q.push_back(make_pair(s,0)); // curr_node curr_dis
    while(!q.empty()) {
        ll cn=q.front().first,cdis=q.front().second;
        for(int i=0;i<g[cn].size();i++) {
            ll ni=g[cn][i].first; ll wi=g[cn][i].second;
            if(cdis+wi<dis[ni]) {
                dis[ni]=cdis+wi;
                q.push_back(make_pair(ni,cdis+wi));
            }
        }
        q.pop_front();
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>s;
    rep(i,n) {
        dis[i]=INF;
    }
    rep(_,m) {
        cin>>u>>v>>w;
        g[u].push_back(make_pair(v,w));
    }
    dijkstra();
    ll forOut=pow(2,31)-1;
    rep(i,n) {
        if(dis[i]!=INF)
            cout<<dis[i]<<" ";
        else
            cout<<forOut<<" ";
    }
    cout<<endl;
    return 0;
}
// AC https://www.luogu.com.cn/record/181870206

第一次提交就基本AC了，没啥心路历程