题解 P4079 【[SDOI2016]齿轮】

· · 题解

看大佬们都说是并查集蒟蒻我真是瑟瑟发抖啊。。。

我写的是分数+gcd

首先假如说让人来处理这件事的话会采用一种什么样的思路呢？

如果是我的话首先会随便找一个点（齿轮）开始，设它的速度为+1

接下来按照给出的边走，一路用“分数”来表达每个齿轮的速度，当要前进的下一个点也被标记了速度，验证新旧两速度是否相同即可。这个思路可以说是简单暴力。。。

再来讨论下复杂度，首先是遍历，不难发现每条边顶多被正反走两边，所以是O(M)，接下来是gcd，如果写的是更相减损法的话就会有稳定的log（100），就是个7左右的常数，总代价可以粗略的理解为100*M 幸好M比较小还是可以过的2333

遍历时要记得有可能不是张连通图

接下来请看看代码吧，希望对你有所帮助！

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int gcd(int a,int b){
    if(a<b)swap(a,b);
    int c;
    while(b){c=a%b;a=b;b=c;}
    return a;
}
struct frnum{
    int s,x,y; //s:0->+ 1->-, x/y
}s[1050];
frnum operator *(frnum A,int b){
    if(b<0){
        A.s^=1;
        b=-b;
    }
    A.x=A.x*b;
    int w=gcd(A.x,A.y);
    A.x/=w;
    A.y/=w;
    return A;
}
frnum operator /(frnum A,int b){
    if(b<0){
        A.s^=1;
        b=-b;
    }
    A.y=A.y*b;
    int w=gcd(A.x,A.y);
    A.x/=w;
    A.y/=w;
    return A;
}
bool operator ==(frnum A,frnum B){
    return A.s==B.s&&A.x==B.x&&A.y==B.y;
}
struct line{
    int nxt,v,x,y;
}e[40000];
int etop,d[1050];
int T,n,m;
void add(int u,int v,int x,int y){
    e[etop].v=v;e[etop].x=x;
    e[etop].y=y;e[etop].nxt=d[u];
    d[u]=etop++;
}
bool vis[1050];
bool f;
void dfs(int u){
    for(int k=d[u];k!=-1;k=e[k].nxt){
        if(vis[e[k].v]){
            if(!(s[u]/e[k].x==s[e[k].v]/e[k].y)){
                f=0;return;
            }
        }
        else{
            vis[e[k].v]=1;
            s[e[k].v]=(s[u]/e[k].x)*e[k].y;
            dfs(e[k].v);
            if(f==0) return;
        }
    }
}
int main(){
    scanf("%d",&T);
    for(int t=1;t<=T;t++){
        printf("Case #%d: ",t);
        memset(s,0,sizeof(s));
        memset(vis,0,sizeof(vis));
        memset(d,-1,sizeof(d));
        etop=0;
        scanf("%d%d",&n,&m);
        for(int i=1,u,v,x,y;i<=m;i++){
            scanf("%d%d%d%d",&u,&v,&x,&y);
            add(u,v,x,y);
            add(v,u,y,x);
        }
        f=1;
        for(int i=1;i<=n;i++)if(!vis[i]){
            s[i].x=s[i].y=1;
            dfs(i);
            if(!f)break;
        }
        if(f) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}