题解 P3386 【【模板】二分图匹配】

发表于 更新于 阅读次数： Waline：
P3386 【【模板】二分图匹配】题解。

考前发个题解涨涨RP

感谢@nederland 巨佬提供了一个网络最大流+邻接矩阵的解法，我就在这里提一下如何优化

原解法：https://www.luogu.org/recordnew/lists?uid=nederland&pid=P3386&status=14&sort=0

可以看到，除第一个AC以外，剩下来的T死……

那么，如何优化呢？

1. 快读+快输！

这个东西，大家都知道，我就不解释了

2. O(3)

虽说NOIP不给用，然而在此题中还是很有用的

3. register

这是一个C++保留字，用来将变量存入内存，加速。

4. 避免变量重复定义

这个东西有效优化时间。比方说一个1000000的循环，你定义一个变量，定义1000000次，不T都怪。相比之下，虽然仍然需要赋值，但减少了重复定义的时间。

用了这些，此题就可以A了啊……

代码：

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
64
#include<cstdio>
#pragma GCC optimize(3)
#define min(x,y) ((y)^(((x)^(y))&(-((x)<(y)))))
bool vis[2005];
int pred[2005],cap[2005][2005],flow[2005][2005],N,t;
inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
template <typename _Tp>
inline void read(_Tp &x){
    int f=1;x=0;char ch=nc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=nc();}
    x*=f;
}
inline void write(long long n){
    if(n==0) return;
    write(n/10);
    putchar(n%10+'0');
}//快读+快输……然而printf比快输还快（我写炸了？）
int findpath(int u,int x){
    if(u==t)return x;
    vis[u]=true;
    for(int v=0;v<N;v++){
        if(!vis[v]){
            int dt=cap[u][v]-flow[u][v];
            if(dt>0){
                pred[v]=u;
                int r=findpath(v,min(x,dt));
                if(r)return r;
            }
        }
    }
    return 0;
}
int main(){
    register int n,m,s,e,r,v,i,u;//优化3、4
    read(n),read(m),read(e);//优化1
    s=0;t=n+m+1;N=n+m+2;
    for(i=1;i<=n;i++)cap[s][i]=1;
    for(i=1;i<=m;i++)cap[n+i][t]=1;
    for(i=0;i<e;i++){
        read(u),read(v);//优化1
        if(u>n||v>m)continue;
        cap[u][v+n]=1;
    }
    while(true){
        for(i=0;i<N;i++)vis[i]=false;
        r=findpath(s,999999999);
        if(!r)break;
        v=t;
        while(v!=s){
            u=pred[v];
            flow[u][v]+=r;
            flow[v][u]-=r;
            v=u;
        }
    }
    register int sum=0;
    for(i=0;i<N;i++)sum+=flow[s][i];
    printf("%d",sum);
    return 0;
}

由@nederland 巨佬的代码优化而来