LCX的算法笔记Week-2

一

题目来源：CCPC威海 https://codeforces.com/gym/103428/problem/G

没想到因为编译语言版本的问题超时了，因为codeforces提交语言太多，就随便选了个C++的，这随便一选就选到了个最慢的😤😤😤😤😤。害我那天晚上看了那么久也没发现问题所在。

这道题是组合数学的一道题，只要把阶乘和求模运算的逆元初始化好，就能求组合数啦。模运算的逆元用到了费马小定理（a（p-1）≡1（mod p））,同时除以a我们就能把a的倒数求模运算的值转换成a(p-2)求模运算的值，然后用快速幂把时间复杂度降下来就行了。很是巧妙。这道题求逆元的时候可以写成下面注释掉的形式，可以少算很多次，实测节省16ms。因为快速幂时间复杂度降到了很低的量级，所以直接求时间也不会长很久。

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
58
59
60
61
62
63
#include <iostream>
using namespace std;
typedef long long LL;
const int N=1e5+10,mod=998244353;
LL fac[N],inv[N];
int tims[N],fa[N],a[N];
LL fpow(LL base,LL p)//快速幂
{
    LL res=1;
    while (p) {
        if (p&1) {
            res=res*base%mod;
        }
        base=base*base%mod;
        p>>=1;
    }
    return res;
}
void init()
{
    fac[0]=inv[0]=1;
    for (int i=1; i<=N-9; i++) {
        fac[i]=i*fac[i-1]%mod;
        inv[i]=fpow(fac[i],mod-2);
    }
//    inv[N-9]=fpow(fac[N-9], mod-2);
//    for (int i=N-10; i>=1; i--) {
//        inv[i]=inv[i+1]*(i+1)%mod;
//    }
}
LL C(int n,int m)
{
    if (m>n) {
        return 0;
    }
     return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    init();
    int n,m,mx=0;
    cin>>n>>m;
    for (int i=0; i<n; i++) {
        cin>>a[i];
        tims[a[i]]++;
        mx=max(mx,a[i]);
    }
    int cnt=0;
    for (int i=0; i<=mx; i++) {
        if (tims[i]) {
            fa[++cnt]=i;
        }
    }
    for (int i=1; i<=m; i++) {
        LL res=1;
        for (int j=1; j<=cnt; j++) {
            res=res*fpow(C(i, fa[j]), tims[fa[j]])%mod;
        }
        cout<<res<<endl;
    }
    return 0;
}

去搜了一下发现了有人跟我有同样的问题

然后就用相同代码手动测试了不同版本语言的编译速度对比

这道题GNU C++20 64位 表现最佳 同样的代码用Clang++17 Diagnostics就会超时

有意思的是我用另一道题测试了一下，发现上道题慢的很多的C++14和不是64位的C++17这道题却相对快了很多。看了下两道题代码区别，上面的函数定义的比较多，下面的没有自定义函数，都是最基本的循环和判断，可能差在这吧。

费马小定理的证明

快速幂模版：

1
2
3
4
5
6
7
8
9
10
11
long long fastPower(long long base, long long power) {
    long long result = 1;
    while (power > 0) {
        if (power & 1) {//此处等价于if(power%2==1)
            result = result * base % 1000;
        }
        power >>= 1;//此处等价于power=power/2
        base = (base * base) % 1000;
    }
    return result;
}

二

题目来源：上海市大学生程序设计竞赛 - 十二月赛

https://acm.ecnu.edu.cn/contest/497/problem/C/

一开始想到的算法思路是正确的，结果因为疏忽一直WA，等终于找到所有错误的时候，发现有一个测试点超时，然后就发现自己用数组来实现的时间复杂度最坏情况是O(m2)，看了下别人ac的代码，发现大部分都是用栈来实现的，就照着原有的思路改进了一下，栈wall维护的是墙上已有的颜色，并且从栈底到栈顶所维护的长度是递减的，单调栈能大大降低时间复杂度，且一个颜色只需要维护最大的那个长度就行了，会减少不必要的特殊情况判断。代码如下

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
#include <iostream>
#include <stack>
using namespace std;
const int M=1e6+10;
typedef pair<int, int> pii;
stack<pii> wall;
int n,m;
bool state[M];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    state[0]=true;
    wall.push({n,0});
    while (m--) {
        int op;
        cin>>op;
        if (op==1) {
            int x,y;
            cin>>x>>y;
            while (wall.size()&&wall.top().first<=x) {
                state[wall.top().second]=false;
                wall.pop();
            }
            if (!state[y]) {
                wall.push({x,y});
                state[y]=true;
            }
        }
        else cout<<wall.size()<<endl;
    }
    return 0;
}

看了一会我发现，只要把原来的代码，也按栈的思路改一下，就能ac啦

注释部分为改动之前超时的代码，和while循环功能差不多（现在看来真是又臭又长，当时为了缩减每次比较次数，删掉一个就把后面的数补过来，减小总次数，但在最坏情况下，即长度一直递减时，相当于没有任何优化。忽略了只要维护的序列是递减的，就一定能使比较的次数最少）

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
#include <iostream>
using namespace std;
const int M=1e6+10;
int n,m,cnt=1;
int color[M],clength[M];
bool state[M];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    clength[0]=n;
    color[1]=0;
    state[0]=true;
    while (m--) {
        int op;
        cin>>op;
        int x,y;
        if (op==1) {
            cin>>x>>y;
            while (cnt&&clength[color[cnt]]<=x) {
                state[color[cnt]]=false;
                cnt--;
            }
//            for (int i=cnt; i>=1; i--) {
//                int c=color[i];
//                if (x>=clength[c]) {
//                    if (c!=y) {
//                        state[c]=false;
//                        color[i]=color[cnt--];
//                        clength[c]=0;
//                    }
//                    if (c==y) {
//                        clength[c]=x;
//                    }
//                }
//            }
            if (!state[y]) {
                color[++cnt]=y;
                clength[y]=x;
                state[y]=true;
            }
        }
        else if (op==2) {
            cout<<cnt<<endl;
        }
    }
    return 0;
}

看了一会我又发现，原来的代码维护的本来就是一个递减序列，但我居然没有想到去判断一下是否停止比较，我加了一行如果不能再比的时候就停止判断的语句。然后就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
#include <iostream>
using namespace std;
const int M=1e6+10;
int n,m,cnt=1;
int color[M],clength[M];
bool state[M];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    clength[0]=n;
    color[1]=0;
    state[0]=true;
    while (m--) {
        int op;
        cin>>op;
        int x,y;
        if (op==1) {
            cin>>x>>y;
            for (int i=cnt; i>=1; i--) {
                int c=color[i];
                if (x>=clength[c]) {
                    if (c!=y) {
                        state[c]=false;
                        color[i]=color[cnt--];
                        clength[c]=0;
                    }
                    if (c==y) {
                        clength[c]=x;
                    }
                }
                else break;//就加了这两个单词就让超时代码过啦，不过上面部分还是很冗余
            }
            if (!state[y]) {
                color[++cnt]=y;
                clength[y]=x;
                state[y]=true;
            }
        }
        else if (op==2) {
            cout<<cnt<<endl;
        }
    }
    return 0;
}

三

题目来源：https://www.luogu.com.cn/problem/P2532

卡特兰数板子题，直观图解：https://www.luogu.com.cn/blog/syksykCCC/solution-p2532

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
#include <bits/stdc++.h>
using namespace std;
const int N=510;
int a[N][N],len=1;
void add(int u)//更新第u个数
{
    for (int i=1; i<=len; i++) {
        a[u][i]+=a[u-1][i];
    }
    for (int i=1; i<=len; i++) {
        a[u][i+1]+=a[u][i]/10;
        a[u][i]%=10;
    }
    if (a[u][len+1]) {
        len++;
    }
}
int main()
{
    int n;
    cin>>n;
    a[1][1]=1;
    for (int i=2; i<=n+1; i++) {
        for (int j=1; j<=i; j++) {
            add(j);
        }
    }
    for (int i=len; i>=1; i--) {
        cout<<a[n][i];
    }
}

四

题目来源： hdu3625

有n个房间，n个钥匙，每个钥匙随机出现在一个房间里，一个房间里有且仅有一个钥匙。我们现在手上没有钥匙，但我们要搜索所有的房间，所以我们有k次机会把一个房间炸开。一号房间里住着一个重要的人，所以一号房间不能炸。给出n，k，求我们能够成功搜索所有房间的概率。

因为拿到一个房间钥匙，就能去打开这个房间里的钥匙所对应那个房间，能构成一个环，所以是第一类Stirling数

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
#include <bits/stdc++.h>
using namespace std;
const int N=25;
int fac[N],stir[N][N];
void init()
{
    fac[1]=1;
    stir[0][0]=1;
    stir[1][1]=1;
    for (int i=2; i<N; i++) {
        fac[i]=fac[i-1]*i;
        for (int j=1; j<=i; j++) {
            stir[i][j]=stir[i-1][j-1]+(i-1)*stir[i-1][j];
        }
    }
}
int main()
{
    init();
    int n,k;
    cin>>n>>k;
    int sum=0;
    for (int i=1; i<=k; i++) {
        sum+=stir[n][i]-stir[n-1][i-1];
    }
    cout<<sum<<' '<<fac[n]<<endl;
    cout<<1.0*sum/fac[n];
}

五

题目来源：hdu2643

Problem Description
Recently in Teddy’s hometown there is a competition named “Cow Year Blow Cow”.N competitors had took part in this competition.The competition was so intense that the rank was changing and changing.
Now the question is:
How many different ways that n competitors can rank in a competition, allowing for the possibility of ties.
Here are the ways when n = 2:
P1 < P2
P2 < P1
P1 = P2

因为可以并列，一个排名相当于一个集合，所以这是个第二类Stirling数

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
#include <bits/stdc++.h>
using namespace std;
const int N=105;
int fac[N],stir2[N][N];
void init()
{
    stir2[0][0]=1;
    fac[0]=1;
    for (int i=1; i<N; i++) {
        fac[i]=i*fac[i-1];
        for (int j=1; j<=i; j++) {
            stir2[i][j]=j*stir2[i-1][j]+stir2[i-1][j-1];
        }
    }
}
int main()
{
    init();
    int n;
    cin>>n;
    int ans=0;
    for (int i=1; i<=n; i++) {
        ans+=stir2[n][i]*fac[i];
    }
    cout<<ans;
}

六

这道题很有意思，求出每种食物的生成函数，然后再乘起来，再泰勒展开，xn前面所对应的系数就是所求结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
const int N=25,mod=10007,inv6=1668;
typedef long long ll;
int main()
{
    string num;
    cin>>num;
    int flag=1;
    ll ans=0;
    for (int i=0; num[i]; i++) {
        if (num[0]=='-') {
            flag=-1;
            continue;
        }
        ans=(ans*10+num[i]-'0')%mod;
    }
    if (flag==-1) {
        ans=-ans;
    }
    cout<<(ans+2)*(ans+1)%mod*(ans)%mod*inv6%mod;
}

一些搜索与图论的模版 全部来源于AcWing

Dijkstra求最短路 朴素版 时间复杂度O(n2)

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
#include <bits/stdc++.h>
using namespace std;
const int N=510;
int dist[N],g[N][N];
bool state[N];
int n,m;
int dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1]=0;
    for (int i=0; i<n-1; i++) {
        int t=-1;
        for (int j=1; j<=n; j++) {
            if (!state[j]&&(t==-1||dist[j]<dist[t])) {
                t=j;
            }
        }
        state[t]=true;
        for (int j=1; j<=n; j++) {
            dist[j]=min(dist[j],dist[t]+g[t][j]);
        }
    }
    if (dist[n]==0x3f3f3f3f) {
        return -1;
    }
    return dist[n];
}
int main() {
    cin>>n>>m;
    memset(g, 0x3f, sizeof g);
    while (m--) {
        int x,y,z;
        cin>>x>>y>>z;
        g[x][y]=min(z,g[x][y]);
    }
    cout<<dijkstra();
    return 0;
}

Dijkstra求最短路 堆优化版 时间复杂度O(nlogn)

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
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int dist[N],h[N],e[N],w[N],ne[N],idx;
bool state[N];
typedef pair<int, int> pii;
priority_queue<pii,vector<pii>,greater<pii>> heap;
int n,m;
int dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    heap.push({0,1});
    dist[1]=0;
    while (heap.size()) {
        auto t=heap.top();
        heap.pop();
        int cur=t.second,distance=t.first;
        if (state[cur]) {
            continue;
        }
        state[cur]=true;
        
        for (int i=h[cur]; i!=-1; i=ne[i]) {
            if (distance+w[i]<dist[e[i]]) {
                dist[e[i]]=distance+w[i];
                heap.push({dist[e[i]],e[i]});
            }
        }
    }
    if (dist[n]==0x3f3f3f3f) {
        return -1;
    }
    return dist[n];
}
void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}
int main() {
    cin>>n>>m;
    memset(h, -1, sizeof h);
    while (m--) {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    cout<<dijkstra();
    return 0;
}

Bellman ford算法求最短路（针对边有负权的状态，时间复杂度O(n2)）

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
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int dist[N],last[N];
struct {
    int a;
    int b;
    int w;
} e[N];
int n,m,k;
void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1]=0;
    for (int i=0; i<k; i++) {
        memcpy(last,dist,sizeof dist);
        for (int j=0; j<m; j++) {
            dist[e[j].b]=min(dist[e[j].b],last[e[j].a]+e[j].w);
        }
    }
}
int main() {
    cin>>n>>m>>k;
    for (int i=0; i<m; i++) {
        int a,b,w;
        cin>>a>>b>>w;
        e[i]={a,b,w};
    }
    bellman_ford();
    if (dist[n]>0x3f3f3f3f/2) {
        cout<<"impossible";
    }
    else cout<<dist[n];
}

spfa算法（对Bellman ford算法的优化，时间复杂度一般情况下O(n),最坏情况下O(n2)）

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
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int dist[N];
bool state[N];
int n,m;
int h[N],ne[N],e[N],w[N],idx;
void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
int spfa()
{
    queue<int> q;
    memset(dist, 0x3f, sizeof dist);
    q.push(1);
    dist[1]=0;
    state[1]=false;
    while (q.size()) {
        int t=q.front();
        q.pop();
        state[t]=false;
        for (int i=h[t]; i!=-1; i=ne[i]) {
            int j=e[i];
            if (dist[j]>dist[t]+w[i]) {
                dist[j]=dist[t]+w[i];
                if(!state[j]){
                    q.push(j);
                    state[j]=true;
                }
            }
        }
    }
    return dist[n];
}
int main() {
    cin>>n>>m;
    memset(h, -1, sizeof h);
    while (m--) {
        int a,b,c;
        cin>>a>>b>>c;
        add(a, b, c);
    }
    int t=spfa();
    if (t>0x3f3f3f3f/2) {
        cout<<"impossible";
    }
    else cout<<t;
}

只需加个cnt数组记录经过的边数，就能用spfa算法判断图中是否存在负环

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
58
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int dist[N],cnt[N];
bool state[N];
int n,m;
int h[N],ne[N],e[N],w[N],idx;
void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
bool spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1]=0;
    queue<int> q;
    for (int i=1; i<=n;i++) {
        q.push(i);
        state[i]=true;
    }
    while (q.size()) {
        int t=q.front();
        q.pop();
        state[t]=false;
        for (int i=h[t]; i!=-1; i=ne[i]) {
            int j=e[i];
            if (dist[j]>dist[t]+w[i]) {
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if (cnt[j]==n) {
                    return true;
                }
                if (!state[j]) {
                    state[j]=true;
                    q.push(j);
                }
            }
        }
    }
    return  false;
}
int main() {
    cin>>n>>m;
    memset(h, -1, sizeof(h));
    while (m--) {
        int a,b,c;
        cin>>a>>b>>c;
        add(a, b, c);
    }
    if (spfa()) {
        cout<<"Yes";
    }
    else cout<<"No";
}

floyd算法求最短路（时间复杂度O(n3)，适用于存在负环的情况）

注意本题要把自环初始化距离为0，因为查询可能会查询自己到自己的距离

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
#include <bits/stdc++.h>
using namespace std;
const int N=210,inf=0x3f3f3f3f;
int dist[N][N];
int n,m,k;
void floyd()
{
    for (int k=1; k<=n; k++) {
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=n; j++) {
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }
}
int main() {
    cin>>n>>m>>k;
    memset(dist, 0x3f, sizeof dist);
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (i==j) {
                dist[i][i]=0;
            }
        }
    }
    while (m--) {
        int x,y,z;
        cin>>x>>y>>z;
        dist[x][y]=min(dist[x][y],z);
    }
    floyd();//不要忘了调用啊！！
    while (k--) {
        int x,y;
        cin>>x>>y;
        if (dist[x][y]>inf/2) {
            cout<<"impossible"<<endl;
        }
        else cout<<dist[x][y]<<endl;
    }
    
}

Prim算法求最小生成树

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
#include <bits/stdc++.h>
using namespace std;
const int N=510,inf=0x3f3f3f3f;
int dist[N],g[N][N];//dist数组维护的是第i个加入集合的点到集合的距离（只是一条边的长度）
int n,m;
bool state[N];
int prim()
{
    int res=0;
    for (int i=0; i<n; i++) {
        int t=-1;
        for (int j=1; j<=n; j++) {
            if (!state[j]&&(t==-1||dist[j]<dist[t])) {
                t=j;//大于小于号不要写错
            }
        }
        state[t]=true;
        if (i&&dist[t]==inf) {
            return inf;
        }
        if (i) {
            res+=dist[t];
        }
        for (int j=1; j<=n; j++) {
            dist[j]=min(dist[j],g[t][j]);
        }
    }
    return res;
}
int main() {
    cin>>n>>m;
    memset(dist, 0x3f, sizeof dist);
    memset(g, 0x3f, sizeof g);
    while (m--) {
        int x,y,z;
        cin>>x>>y>>z;
        g[x][y]=g[y][x]=min(g[x][y],z);
    }
    int t=prim();//这里的函数只能调用一次，不能调用一次取一次值，值会发生变化
    if (t==inf) {
        cout<<"impossible";
    }
    else cout<<t<<endl;
}

Kruskal算法求最小生成树

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 <bits/stdc++.h>
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f;
int n,m;
int res,cnt;
int p[N];
struct edge{
    int u,v,w;
    bool operator <(const edge & x)const
    {
        return w<x.w;
    }
} e[N];
int find(int x)
{
    if (p[x]!=x) {
        p[x]=find(p[x]);
    }
    return p[x];
}
int main() {
    cin>>n>>m;
    for (int i=0; i<m; i++) {
        int u,v,w;
        cin>>u>>v>>w;
        e[i]={u,v,w};
    }
    for (int i=1; i<=n; i++) {
        p[i]=i;
    }
    sort(e,e+m);
    for (int i=0; i<m; i++) {
        int a = e[i].u, b = e[i].v, w =e[i].w;
        a=find(a);
        b=find(b);
        if (a!=b) {
            p[a]=p[b];//这里是把父节点的父节点变成另一个集合的父节点来完成集合的合并
            res+=w;
            cnt++;
        }
    }
    if (cnt<n-1) {
        cout<<"impossible";
    }
    else cout<<res;
}

染色法判定二分图

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
#include <iostream>
using namespace std;
const int N=1e5+10,M=2e5+10;
int n,m;
int color[N];
int h[N],ne[M],e[M],idx;
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
bool dfs(int a,int c)
{
    color[a]=c;
    for (int i=h[a]; i!=-1; i=ne[i]) {
        int j=e[i];
        if (!color[j]) {
            if (!dfs(j, 3-c)) {
                return  false;
            }
        }
        else if (color[j]==c) return false;
    }
    return true;
}
int main() {
    cin>>n>>m;
    memset(h, -1, sizeof h);
    while (m--) {
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    bool flag=true;
    for (int i=1; i<=n; i++) {
        if (!color[i]) {
            if (!dfs(i, 1)) {
                flag=false;
                break;
            }
        }
    }
    if (flag) {
        cout<<"Yes";
    }
    else cout<<"No";
}

匈牙利算法-二分图的最大匹配

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
#include <iostream>
#include <cstring>
using namespace std;
const int N=510,M=1e5+10;
int n1,n2,m;
int match[N];
bool st[N];
int h[N],ne[M],e[M],idx;
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
bool find(int a)
{
    for (int i=h[a]; i!=-1; i=ne[i]) {
        int j=e[i];
        if (!st[j]) {
            st[j]=true;
            if (match[j]==0||find(match[j])) {
                match[j]=a;
                return true;
            }
        }
    }
    return false;
}
int main() {
    memset(h, -1, sizeof h);
    cin>>n1>>n2>>m;
    while (m--) {
        int u,v;
        cin>>u>>v;
        add(u,v);
    }
    int res=0;
    for (int i=1; i<=n1; i++) {
        memset(st, false, sizeof st);
        if (find(i)) {
            res++;
        }
    }
    cout<<res;
}