为什么这道题只能这样写
//2021/7/18
//2021/7/23
#include <cstdio>
#include <cstring>
using namespace std;
const int ma=250000;
struct Node
{
int v;
int nxt;
};
Node node[ma<<1];
int head[ma],mat[ma];
bool vis[ma];
int idx;
int l,r,m;
inline void add(int u,int v)
{
node[++idx].v=v;
node[idx].nxt=head[u];
head[u]=idx;
}
inline bool get_edge(int u)
{
for(register int i=head[u];i;i=node[i].nxt)
{
int j=node[i].v;
if(vis[j]==false)
{
vis[j]=true;
if(mat[j]==0 || get_edge(mat[j])==true)
{
mat[j]=u;
return true;
}
}
}
return false;
}
int main(void)
{
scanf("%d%d%d",&l,&r,&m);
while(m--)
{
int u,v;
scanf("%d%d",&u,&v);
add(v,u);
}
int res=0;
for(register int i=1;i<=r;i++)
{
memset(vis,false,sizeof(vis));
if(get_edge(i)==true)
{
res++;
}
}
printf("%d\n",res);
for(register int i=1;i<=l;i++)
{
printf("%d\n",mat[i]);
}
return 0;
}
而不能这样写
//2021/7/18
//2021/7/23
#include <cstdio>
#include <cstring>
using namespace std;
const int ma=250000;
struct Node
{
int v;
int nxt;
};
Node node[ma<<1];
int head[ma],mat[ma];
bool vis[ma];
int idx;
int l,r,m;
inline void add(int u,int v)
{
node[++idx].v=v;
node[idx].nxt=head[u];
head[u]=idx;
}
inline bool get_edge(int u)
{
for(register int i=head[u];i;i=node[i].nxt)
{
int j=node[i].v;
if(vis[j]==false)
{
vis[j]=true;
if(mat[j]==0 || get_edge(mat[j])==true)
{
mat[j]=u;
return true;
}
}
}
return false;
}
int main(void)
{
scanf("%d%d%d",&l,&r,&m);
while(m--)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
int res=0;
for(register int i=1;i<=l;i++)
{
memset(vis,false,sizeof(vis));
if(get_edge(i)==true)
{
res++;
}
}
printf("%d\n",res);
for(register int i=1;i<=r;i++)
{
printf("%d\n",mat[i]);
}
return 0;
}
其中不一样的地方在于:
ac:add(v,u);
wa:add(u,v);
ac:
for(register int i=1;i<=r;i++)
{
memset(vis,false,sizeof(vis));
...
}
wa:
for(register int i=1;i<=l;i++)
{
...
}
ac:
for(register int i=1;i<=l;i++)
{
printf("%d\n",mat[i]);
}
wa:
for(register int i=1;i<=r;i++)
{
...
}
wa 的那种写法在洛谷上可以 AC,而且我感觉逻辑没啥问题。。