求Hack或调题
#include<stdio.h>
#define P 998244353
int abs(int x)
{
return (x<0?-x:x);
}
int qpow(int a,int b)
{
long long r;
if(b==1)
{
return a;
}
r=qpow(a,b/2);
if(b&1)
{
return r*r%P*(long long)a%P;
}
else
{
return r*r%P;
}
}
int speed[1000],sign[1000];
int head[1000],to[20000],next[20000],weighta[20000],weightb[20000],gm;
void add_edge(int f,int t,int wa,int wb)
{
gm[next]=f[head];
f[head]=gm;
gm[to]=t;
gm[weighta]=wa;
gm[weightb]=wb;
gm++;
}
int vis[1000],err;
void dfs(int s,int b)
{
int i,spd,sgn;
for(i=s[head];i!=-1&&!err;i=i[next])
{
spd=(long long)qpow(abs(i[weightb]),P-2)*abs(i[weighta])%P*(long long)s[speed]%P;
sgn=s[sign]*i[weighta]/abs(i[weighta])*i[weightb]/abs(i[weightb]);
// printf("N%d -> %d:i%d\t\tspd%d\t\tsgn%d\b \n",s+1,i[to]+1,i,spd,sgn);
if(i[to][vis]!=b)//visited
{
// printf("CHK:SPD%d\tOSPD%d\tSGN:%d\tOSGN:%d\n",spd,i[to][speed],sgn,i[to][sign]);
if(spd!=i[to][speed]||sgn!=i[to][sign])
{
err=1;
// printf("Error!\n");
}
}
else
{
i[to][speed]=spd;
i[to][sign]=sgn;
i[to][vis]=b^1;
dfs(i[to],b);
}
}
}
void func(int x)
{
gm=0;
err=0;
int n,m,i,r,t,wa,wb;
scanf("%d%d",&n,&m);
for(i=0;i<n;++i)
{
i[head]=-1;
}
for(i=0;i<m;++i)
{
scanf("%d%d%d%d",&r,&t,&wa,&wb);
r--;
t--;
add_edge(r,t,wa,wb);
add_edge(t,r,wb,wa);
}
for(i=0;i<n;++i)
{
if(i[vis]==(x&1)&&!err)
{
i[vis]=(x&1)^1;
i[speed]=1;
i[sign]=1;
dfs(i,x&1);
}
}
printf("Case #%d: ",x+1);
if(err)
{
printf("No");
}
else
{
printf("Yes");
}
printf("\n");
}
int main()
{
int n,i;
scanf("%d",&n);
for(i=0;i<n;++i)
{
func(i);
}
return 0;
}
它只会把正确的情况误判成错误的,C码风有点独特,看不懂就求hack,可以用gcc/g++编译。