题解 P2913 【[USACO08OCT]车轮旋转Wheel Rotation】

NTG_Adiord · 2018-08-15 09:42:14 · 题解

鬼畜做法

反正跟顺序根本没多大关系。。。。。直接1抑或和就好

代码如下

#include <cstdio>
int main(){
    int n,a;bool b;
    scanf("%d",&n);n--;
    while(n--)scanf("%d%d%d",&a,&a,&a),b^=a;
    printf("%d",b);
}

太鬼畜了真是

麻烦的做法

链式前向星，记录一下引擎之前是否有动力轮，如果没有那说明这个轮子是第一个轮子

然后遍历算抑或和就完了

详情请咨询10086

详情参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
int l;
int to[1001];
int hea[1001];
int nex[1001];
int wea[1001];
int in[1001];
int ans;
void dr(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        in[b]++;//记录是否被连接
        to[++l]=b;nex[l]=hea[a];hea[a]=l,wea[l]=w;//连边，懒得写建边函数了
    }
}
void wk(){
    for(int i=1;i<=n;i++){
        if(in[i]==0){
            for(int j=i;j;j=to[hea[j]]){
                ans=ans^wea[hea[j]];//两次相反为0,直接算抑或，1^1=0
            }
        }
        printf("%d",ans);
        return;//直接返回
    }
}
int main(){
    dr();//读入
    wk();//输出
    return 0;
}