dfs判定一下就没了
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=20005;
const long double eps=1e-8;
int t,n,m,h[N],vis[N],en,flag;
long double dep[N];
bool d[N];
struct Edge{
int b,next;
long double l1,l2;
bool l;
}e[N];
void AddEdge(int sa,int sb,int sc,int sd,bool se){
e[++en].b=sb;
e[en].l1=sc;
e[en].l2=sd;
e[en].l=se;
e[en].next=h[sa];
h[sa]=en;
}
void DFS(int u,int fa){
vis[u]=1;
for(int i=h[u];i && !flag;i=e[i].next){
int v=e[i].b;
if(v==fa)continue;
if(!vis[v]){
d[v]=(d[u]^e[i].l);
dep[v]=dep[u]+log(e[i].l2)-log(e[i].l1);
DFS(v,u);
}
else {
if(d[v]!=(d[u]^e[i].l) || fabs(dep[u]-dep[v]+log(e[i].l2)-log(e[i].l1))>eps){flag=1;return;}
}
}
}
int main(){
freopen("4602.in","r",stdin);
freopen("4602.out","w",stdout);
scanf("%d",&t);
for(int i=1;i<=t;i++){
scanf("%d %d",&n,&m);
memset(vis,0,sizeof(vis));
memset(h,0,sizeof(h));
en=flag=0;
for(int j=1;j<=m;j++){
int u,v,x,y;
scanf("%d %d %d %d",&u,&v,&x,&y);
if(y<0){AddEdge(u,v,x,-y,1);AddEdge(v,u,-y,x,1);}
else {AddEdge(u,v,x,y,0);AddEdge(v,u,y,x,0);}
}
for(int j=1;j<=n && !flag;j++)if(!vis[j]){dep[j]=0;DFS(j,j);}
printf("Case #%d: %s\n",i,flag?"No":"Yes");
}
return 0;
}
评论 (0)
