题解 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了啊…… 代码： ```cpp #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 巨佬的代码优化而来 求过，~~我觉得我介绍了除女装之外的所有优化了~~