~~说不定你写个快读就卡过了呢~~
by hjqhs @ 2023-05-01 10:06:46
@[wxh666](/user/342494) 或者再加一点指令集优化 /kk
by hjqhs @ 2023-05-01 10:08:16
@[hjqhs](/user/724988) 过了,正好1s,多一毫秒都不行,我想看看为什么耗时这么长
by wxh666 @ 2023-05-01 10:14:10
$menset$ 的时间复杂度是 $O(n)$ 的
判断里面套的 $dfs$ 函数也是 $O(n)$ 的
by wsr_jason @ 2023-05-01 10:44:43
[下面改后的代码(点击查看提交记录)](https://www.luogu.com.cn/record/109307930)
```
#include<bits/stdc++.h>
using namespace std;
typedef int lsqxx;
struct lq {
lsqxx v,nxt;
} e[500005];
lsqxx h[1005],cnt;
void add(int u,int v) {
e[++cnt].v=v;
e[cnt].nxt=h[u];
h[u]=cnt;
}
int re[1005],vis[1005],dis[1005];
int dt[505][505];
int n,m,E,ans;
int x,y;
int flag=0;
bool dfs(int t) {
for(int i=h[t]; i; i=e[i].nxt) {
int v=e[i].v;
if(re[v]==t) continue;
if(dis[v]) continue;
dis[v]=1;
if(!vis[v]) {
re[v]=t;
vis[v]=1;
return true;
} else {
if(dfs(re[v])) {
// dis[v]=1;
vis[v]=1;
re[v]=t;
return true;
}
}
}
return false;
}
int main() {
cin>>n>>m>>E;
for(int i=1; i<=E; i++) {
scanf("%d%d",&x,&y);
// if(dt[x][y])
// continue;
// else
add(x,y+n);//,dt[x][y]=1;
}
for(int i=1; i<=n; i++) {
// for(int j=h[i]; j; j=e[j].nxt) {
// int v=e[j].v;
// if(!vis[v]) {
// re[v]=i;
// vis[v]=1;
// ans++;
// break;
// } else {
memset(dis,0,sizeof(dis));
// dis[v]=1;
// if(dfs(re[v])) {
if(dfs(i)) {
ans++;
// vis[v]=1;
// re[v]=i;
// break;
// } else
// continue;
// }
}
}
cout<<ans;
return 0;
}
```
很多东西是没有必要写的,删一删就能跑的很快(最慢$24ms$)
by gxp123 @ 2023-05-01 10:58:03
@[gxp123](/user/408602) 妙啊,谢谢
by wxh666 @ 2023-05-01 11:20:23