题解

43 条题解

  • 0
    @ 2009-05-16 17:52:21

    哦,对的。

  • -1
    @ 2017-09-29 19:43:22

    吉儿小朋友,你会分我一点钱吗?
    月亮之眼价值连城吧……
    我帮你修好了……
    记得给钱啊……
    c++
    、、、、、、、
    #include<iostream>
    #include<cstdio>
    #define maxn 505
    using namespace std;
    int p[maxn],v[maxn],N,M;
    int find(int x){
    int t=p[x];
    if(t==x) return x;
    v[x]+=v[t];
    return p[x]=find(t);
    }
    int merg(int x,int y,int l){
    int fx=find(x),fy=find(y),d;
    d=v[x]+l-v[y];
    if(fx!=fy){
    if(d>=0) p[fy]=fx, v[fy]=d;
    else p[fx]=fy, v[fx]=-d;
    }
    else if(v[x]+l != v[y]) return -1;
    return 1;
    }
    int main(){
    int a,b,c,tmp;
    for(int i=0;i<=maxn-2;i++) v[i]=0, p[i]=i;
    scanf("%d%d",&M,&N);
    for(int i=0;i<N;i++){
    scanf("%d%d%d",&a,&b,&c);
    if(merg(a,b,c)==-1){printf("-1\n"); return 0;}
    }
    for(int i=1;i<=M;i++) find(i);
    for(int i=1;i<=M;i++) printf("%d\n",v[i]);
    return 0;
    }

  • -1
    @ 2016-08-16 11:25:42

    ###U43君又来水题解啦!
    pascal
    var
    r1,r2,l,h:array[0..501]of longint;
    flag:array[0..501]of boolean;//记录有没有被搜到
    i,n,p,min:longint;
    procedure search(step:longint);
    var
    i,x,tall:longint;
    begin
    flag[step]:=true;
    for i:=1 to p do
    if (r1[i]=step)or(r2[i]=step) then begin
    x:=r1[i]+r2[i]-step;
    if r1[i]=step then tall:=h[step]+l[i] else tall:=h[step]-l[i];计算另一个珠子的高度
    if (flag[x]=true)and(h[x]<>tall) then begin//如果两个珠子间连接了不止一条线,那么一定无解,原因自己思考
    write(-1);
    halt;
    end;
    h[x]:=tall;
    if not flag[x] then search(x);//搜下一个没有被搜到的珠子
    end;
    end;
    begin
    readln(n,p);
    for i:=1 to p do readln(r1[i],r2[i],l[i]);
    h[1]:=0;
    search(1);
    min:=maxlongint;
    for i:=1 to n do
    if h[i]<min then min:=h[i];
    if min<0 then
    for i:=1 to n do h[i]:=h[i]-min;//防止珠子掉到海平面下面去了
    for i:=1 to n do writeln(h[i]);
    end.

    其实用并查集也可以的。
    下面是搜索的评分:
    测试数据 #0: Accepted, time = 0 ms, mem = 816 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 820 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 820 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 816 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 820 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 816 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 816 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 820 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 816 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 816 KiB, score = 10
    Accepted, time = 0 ms, mem = 820 KiB, score = 100
    #搜索是可以0ms通过的!!!!
    ###输出-1能得20分,也是0ms,但是我的搜索0ms满分呵呵呵~

信息

ID
1540
难度
5
分类
图结构 | 差分约束图结构 | 拓扑排序 点击显示
标签
递交数
1360
已通过
429
通过率
32%
被复制
2
上传者