题解 P4079 【[SDOI2016]齿轮】

· · 题解

做题需要一点暴力的勇气......

一看n只有这么点大，我就把什么并查集什么逆元忽略了，直接染色加宽搜走一波

然而打下来只有70分，错的还是前三个点......我抓破脑袋想不出来哪儿错了，召唤前排神犇LRL52搞了一会儿也没什么结果......于是果断去隔壁loj.ac搞了数据来debug，最后发现还是我和LRL52都坚信不会错的重链判断上凉了......

所以果然......越自信越容易出事儿骄傲自满必翻车by陈毅 不废话了，上代码

#include<bits/stdc++.h>
using namespace std;
std::vector<int>G[1005];
std::vector<double>W[1005];
int N,M,vis[1005];
double eps=1e-5,cnt[1005];//eps不能太小

struct node{
    int id;//这是id号齿轮 
    double circle;//它现在转了circle圈 
};

bool BFS(){
    for(int i=1;i<=N;i++){
        if(vis[i])continue;//这个vis其实有点像一个并查集（其实就是染色），可以保证对于一个集合只搜索一次（这个组可能划分成多个毫不相关的集合嘛）
        node c;
        c.circle=cnt[i]=1;
        c.id=i;
        vis[i]=1;//初始化
        queue<node>Q;
        Q.push(c);
        while(!Q.empty()){
            node u=Q.front();
            Q.pop();
            for(int i=0;i<G[u.id].size();i++){
                int v=G[u.id][i];
                double cc=u.circle*W[u.id][i];//注意一下W[i][j]的第二维，想一想为什么不直接用v
                if(!vis[v]){
                    vis[v]=1;
                    cnt[v]=cc;
                    Q.push(node{v,cc});
                }
                else if(fabs(cc-cnt[v])>eps)return false;//入过队列了就只判断符合条件与否了，再入队的话就没完没了了（@李溢出）
            }
        }
    }
    return true;//如果都没问题就true了呗
}

int main(){
    //freopen("in.txt","r",stdin);
    int T;
    scanf("%d",&T);
    for(int kkk=1;kkk<=T;kkk++){//不要在意细节
        memset(vis,0,sizeof(vis));
        memset(W,0,sizeof(W));
        memset(cnt,0,sizeof(cnt));
        scanf("%d%d",&N,&M);
        for(int i=1;i<=N;i++)
        G[i].clear();
        for(int i=1,u,v,x,y;i<=M;i++){
            scanf("%d%d%d%d",&u,&v,&x,&y);
            G[u].push_back(v);
            G[v].push_back(u);
            W[u].push_back((double)y/x);//这里要保证比例是一条一条链对应过去的，否则以两个齿轮的id保存的话会使不同的链用同一个比例
            W[v].push_back((double)x/y);//双向边是要建的
        }
        if(BFS())printf("Case #%d: Yes\n",kkk);
        else printf("Case #%d: No\n",kkk);
    }
    return 0;
}

于是就完事儿了。我去看LXL翻车了(hiahiahia)。