题解

43 条题解

  • 1
    @ 2019-05-07 19:05:12

    DFS,向上负边,向下正边,注意检查组成的环满不满足条件。数据量不大,O(NP)也过了。

    #include <iostream>
    
    using namespace std;
    
    typedef struct
    {
        int h,l,d;
    }edge;
    
    edge e[500];
    int high[501]={0};
    bool vis[501]={0};
    int n,p;
    bool check=true;
    
    void dfs(int x)
    {
        if(!vis[x])
        {
            vis[x]=true;
            int i;
            for(i=0;i<p;i++)
            {
                if(e[i].h==x)
                {
                    if(vis[e[i].l])
                    {
                        check=check&&(high[e[i].l]==high[x]+e[i].d);
                    }
                    else
                    {
                        high[e[i].l]=high[x]+e[i].d;
                        dfs(e[i].l);
                    }
                }
                if(e[i].l==x)
                {
                    if(vis[e[i].h])
                    {
                        check=check&&(high[e[i].h]==high[x]-e[i].d);
                    }
                    else
                    {
                        high[e[i].h]=high[x]-e[i].d;
                        dfs(e[i].h);
                    }
                }
            }
        }
    }
    
    int main()
    {
        int i;
        cin>>n>>p;
        for(i=0;i<p;i++)
        {
            cin>>e[i].h>>e[i].l>>e[i].d;
        }
        dfs(1);
        if(!check)
        {
            cout<<-1<<endl;
            return 0;
        }
        for(i=1;i<=n;i++)
        {
            if(!vis[i])
            {
                cout<<-1<<endl;
                return 0;
            }
        }
        int hist=0;
        for(i=1;i<=n;i++)
        {
            hist=min(hist,high[i]);
        }
        if(hist<0)
        {
            for(i=1;i<=n;i++)
            {
                high[i]-=hist;
            }
        }
        for(i=1;i<=n;i++)
        {
            cout<<high[i]<<endl;
        }
        return 0;
    }
    
  • 1
    @ 2016-08-28 22:47:43

    U41君也来啦!

    var
    n,m,x,y,z,k,i,j:longint;
    a,b,a1:array [0..501,0..501] of longint;
    ok:boolean;
    begin
    readln(n,m);
    filldword(a,sizeof(a) div 3,maxint);
    for i:=1 to m do
    begin
    readln(x,y,z);
    a[y,x]:=-z;a[x,y]:=z;
    b[y,x]:=1;b[x,y]:=1;
    end;

    a1:=a;
    for k:=1 to n do
    for i:=1 to n do
    for j:=1 to n do
    if (i<>j) and (j<>k) and (k<>i) then
    begin
    b[i,j]:=b[i,j] or (b[i,k] and b[k,j]);
    if (a[i,k]<>maxint) and (a[k,j]<>maxint)then
    a[i,j]:=a[i,k]+a[k,j];
    end;

    for i:=1 to n do
    for j:=1 to n do
    if (a[i,j]<>a1[i,j]) and (a1[i,j]<>maxint) then begin writeln(-1);exit;end;
    for i:=1 to n do
    begin
    ok:=true;
    for j:=1 to n do if (a[i,j]<=0) and (j<>i) then begin ok:=false;break;end;
    if ok then
    begin
    a[i,i]:=0;
    for j:=1 to n do writeln(abs(a[i,j]));
    exit;
    end;
    end;
    end.

  • 1
    @ 2016-07-18 19:50:39

    SPFA秒杀
    var n,p,i,j,x,y,z,min:longint;
    f,t:array[0..501,0..501] of longint;
    q:array[0..100001] of longint;
    v:array[0..100001] of boolean;
    d,times:array[0..501] of longint;
    flag:boolean;
    procedure spfa;
    var i,x,head,tail:longint;
    begin
    fillchar(q,sizeof(q),0);
    head:=0; tail:=1;
    fillchar(v,sizeof(v),false);
    for i:=1 to n do d[i]:=maxlongint div 3;
    q[1]:=1; v[1]:=true; d[1]:=0;
    while head<>tail do
    begin
    head:=head+1; x:=q[head]; v[x]:=false;
    for i:=1 to n do
    if (t[x,i]=1)and(d[x]+f[x,i]<d[i]) then
    begin
    d[i]:=d[x]+f[x,i];
    inc(times[i]);
    if times[i]>=2 then
    begin
    writeln('-1');
    halt;
    end;
    if not(v[i]) then
    begin
    tail:=tail+1;
    q[tail]:=i;
    v[i]:=true;
    end;
    end;
    end;
    end;
    begin
    readln(n,p);
    for i:=1 to p do
    begin
    readln(x,y,z);
    f[x,y]:=z; f[y,x]:=-z;
    t[x,y]:=1; t[y,x]:=1;
    end;
    spfa; flag:=true;
    min:=maxlongint div 3;
    for i:=1 to n do
    begin
    if min>d[i] then min:=d[i];
    if d[i]=maxlongint div 3 then flag:=false;
    end;
    if not flag then
    begin
    writeln('-1');
    halt;
    end;
    for i:=1 to n do d[i]:=d[i]-min;
    for i:=1 to n do writeln(d[i]);
    end.

  • 1
    @ 2016-05-31 19:57:43

    并查集
    A是B的双亲就表示A的位置比B的高,对于每个节点保存当前到双亲节点的距离(为正值),这样在并查集的树中,根节点与一个孩子的孩子的孩子.....的孩子的距离就可以在路径压缩的过程中计算出来:
    对于两个不同集合的合并,由于在找集合的过程中使用了find函数,所以相关节点一定直接和集合树的根节点连接。设现在要连接的节点是a、b,它们的根节点分别是roota和rootb, a与b的距离为c, a在b的上面。集合的合并是集合根节点之间的连接,所以需要计算出根节点之间的距离P,b到roota的距离应为d[a]+c, b到rootb的距离为d[b] ,假设rootb成为roota的孩子,着P+d[b]=d[a]+c => P=d[a]+c-d[b].若P为负,则roota应成为roota的孩子,距离为P的绝对值。
    //转载于http://www.cnblogs.com/wuminye/p/3182467.html
    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;
    }

    测试数据 #0: Accepted, time = 0 ms, mem = 564 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 556 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 560 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 560 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 556 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 560 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 556 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 560 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 556 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 560 KiB, score = 10

  • 1
    @ 2015-10-13 20:53:55

    program a03;
    type
    re=^pp;
    pp=record
    a,b:longint;
    d:re;
    end;
    var
    i,j,k,l,n,m,g,h:longint;
    pa:array[0..1000]of re;
    dis,dui,diss:array[0..1000]of longint;
    vis:array[0..1000]of boolean;

    procedure he(x,y,z:longint);
    var
    p:re;
    begin
    p:=pa[x];
    new(pa[x]);
    pa[x]^.a:=y;
    pa[x]^.b:=z;
    pa[x]^.d:=p;
    end;

    procedure spfa(x:longint);
    var
    i,k,l,r:longint; p:re;
    begin
    for i:=1 to n do
    begin
    dis[i]:=maxlongint div 3;
    vis[i]:=false;
    end;
    vis[x]:=true; dis[x]:=0;
    l:=0; r:=1; dui[r]:=x;
    while l<r do
    begin
    if l>1000 then begin writeln(-1); halt; end;
    inc(l);
    k:=dui[l];
    p:=pa[k];
    while p<>nil do
    begin
    if dis[p^.a]>dis[k]+p^.b then
    begin
    dis[p^.a]:=dis[k]+p^.b;
    if vis[p^.a]=false then
    begin
    vis[p^.a]:=true;
    inc(r);
    dui[r]:=p^.a;
    end;
    end;
    p:=p^.d;
    end;
    vis[k]:=false;
    end;
    end;

    begin
    readln(n,m);
    for i:=1 to m do
    begin
    readln(k,l,g);
    he(k,l,g);
    he(l,k,-g);
    end;
    spfa(1);
    k:=maxlongint; l:=0;
    for i:=1 to n do
    if dis[i]<k then
    begin
    k:=dis[i];
    l:=i;
    end;

    for i:=1 to n do
    if i=l then
    writeln(0) else
    writeln(dis[i]-dis[l]);
    end.

  • 0
    @ 2017-11-20 21:59:27

    上->下正权边
    下->上负权边
    即可
    #include<iostream>
    #include<stdio.h>
    #include<algorithm>
    using namespace std;
    #define MAXN 5000
    #define INF 10000000
    int n,p,highest,ans;
    int f[MAXN],dis[505][MAXN],rdis[505][MAXN];
    struct Node
    {
    int a,b,w;
    }road[MAXN];
    int cmp(Node x,Node y)
    {
    return x.a<y.a;
    }
    void init()
    {
    int i,ri1,ri2,li;
    scanf("%d %d",&n,&p);
    for(i=1;i<=p;i++)
    {
    scanf("%d %d %d",&ri1,&ri2,&li);
    road[2*i-1].a=ri1; road[2*i].a=ri2;
    road[2*i-1].b=ri2; road[2*i].b=ri1;
    road[2*i-1].w=li; road[2*i].w=-li;
    }
    sort(road+1,road+2*p+1,cmp);
    for(i=1;i<=2*p;i++) if(!f[road[i].a]) f[road[i].a]=i;
    f[n+1]=2*p+1;
    for(i=n;i>=1;i--) if(!f[i]) f[i]=f[i+1];
    }
    int spfa(int s)
    {
    int q[MAXN],v[MAXN];
    int maxn,h,t,i,x,y;
    for(i=1;i<=n;i++)
    {
    v[i]=0;
    dis[s][i]=INF;
    }
    dis[s][s]=0;
    h=0;
    t=1;
    q[t]=s;
    v[s]=1;
    while(h!=t)
    {
    h=(h+1)%(n+1);
    x=q[h];
    v[x]=0;
    for(i=f[x];i<f[x+1];i++)
    {
    y=road[i].b;
    if(dis[s][y]!=INF && dis[s][x]+road[i].w!=dis[s][y]) return -1;
    if(dis[s][x]+road[i].w<dis[s][y])
    {
    dis[s][y]=dis[s][x]+road[i].w;
    if(!v[y])
    {
    t=(t+1)%(n+1);
    q[t]=y;
    v[y]=1;
    }
    }
    }
    }
    for(i=1;i<=n;i++) if(dis[s][i]<0) return 0;
    return 1;
    }
    void work()
    {
    int i,t;
    ans=0;
    for(i=1;i<=n;i++)
    {
    t=spfa(i);
    if(t==-1)
    {
    printf("-1\n");
    return;
    }
    else if(t)
    {
    highest=i;
    break;
    }
    }
    //cout<<highest<<endl;
    for(i=1;i<=n;i++) printf("%d\n",dis[highest][i]);
    }
    int main()
    {
    init();
    work();
    return 0;
    }

  • 0
    @ 2016-08-06 19:51:51

    感觉这题分类弄错了。\(O(n+m)\) 的搜索即可完成任务。因为数据量小所以写了个\(O(n^2)\)的也能秒杀。
    方法:若 u 和 v 通过一条长为 L 的线连在一起且 u 在 v 上方,则连边 u->v、v->u,边权分别为 L 和 -L。设数组 height,令 height[i] 代表 i 号珍珠的高度,越靠上值越小。然后假定 height[1] = 0,从 1 号点开始搜索,把所有点遍历一次并得到每个点的 height ,若有后向边则判断是否合法。跑完搜索后,height 数组存储的是每个点**相对于 1 号点**的高度。根据题目要求,需要令最高点高度为零。所以只需找出 height 数组的最小值 min,然后把每个点的高度减去 min 即可。

    • @ 2019-01-07 22:08:33

      帮忙看看这个为什么第一组和最后一组数据一直是runtime error
      #include<stdio.h>

      struct Line
      {
      int r1,r2,l;
      }line[10000];

      int main()
      {
      int INF=100000000;
      int max,i,j,h[10000]={0},pos,flag=0,flag1=0,t,m;
      int n,p;
      scanf("%d%d",&n,&p);
      for(i=1;i<=n;i++)
      {
      h[i]=INF;
      }
      for(i=0;i<p;i++)
      {
      scanf("%d%d%d",&line[i].r1,&line[i].r2,&line[i].l);
      }
      h[1]=0;
      max=0;
      pos=1;

      for(i=0;i<p;i++)
      {
      if(line[i].r1==1)
      {
      t=line[i].r2;
      if(h[t]!=INF&&h[t]!=h[1]-line[i].l)
      {
      flag=1;
      break;
      }
      h[t]=h[1]-line[i].l;
      if(max<h[t])
      {
      max=h[t];
      pos=t;
      }
      }
      else if(line[i].r2==1)
      {
      t=line[i].r1;
      if(h[t]!=INF&&h[t]!=h[1]+line[i].l)
      {
      flag=1;
      break;
      }
      h[t]=h[1]+line[i].l;
      if(max<h[t])
      {
      max=h[t];
      pos=t;
      }
      }
      }
      if(flag==1)
      {
      printf("-1\n");
      return 0;
      }
      for(j=2;j<=n;j++)
      {
      // flag=0;
      for(i=0;i<p;i++)
      {

      t=line[i].r1;
      m=line[i].r2;
      if(h[t]!=INF&&h[m]!=INF&&h[m]!=h[t]-line[i].l)
      {
      printf("-1");
      return;
      }
      if(h[m]==INF&&h[t]!=INF)
      {
      h[m]=h[t]-line[i].l;
      if(max<h[m])
      {
      max=h[m];
      pos=m;
      }
      }
      else if(h[m]!=INF&&h[t]==INF)
      {
      h[t]=h[m]+line[i].l;
      if(max<h[t])
      {
      max=h[t];
      pos=t;
      }
      }
      }
      }
      for(i=1;i<=n;i++)
      {
      if(h[i]==INF)
      {
      printf("-1");
      return;
      }
      }
      for(i=1;i<=n;i++)
      {
      h[i]=max-h[i];
      printf("%d\n",h[i]);
      }
      return 0;
      }

  • 0
    @ 2016-05-22 21:39:57

    编译成功

    Free Pascal Compiler version 3.0.0 [2015/11/16] for i386
    Copyright (c) 1993-2015 by Florian Klaempfl and others
    Target OS: Win32 for i386
    Compiling foo.pas
    foo.pas(6,28) Note: Local variable "k" is assigned but never used
    Linking foo.exe
    82 lines compiled, 0.0 sec, 28160 bytes code, 1268 bytes data
    1 note(s) issued
    测试数据 #0: Accepted, time = 0 ms, mem = 820 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 824 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 828 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 824 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 828 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 828 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 824 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 824 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 824 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 824 KiB, score = 10
    Accepted, time = 0 ms, mem = 828 KiB, score = 100
    返回代码界面 | 关闭
    program p1540;
    type tnode=record
    long,next,go:longint;
    end;

    var n,m,x,y,z,i,etree,temp,k:longint;
    dis,h,change:array [0..505] of longint;
    exist:array [0..505] of boolean;
    team:array [0..1050] of longint;
    e:array [0..1050] of tnode;

    procedure ins(a,b,c:longint);
    begin
    inc(etree);
    e[etree].long:=c;
    e[etree].next:=h[a];
    e[etree].go:=b;
    h[a]:=etree;
    end;

    procedure print;
    begin
    writeln(-1);
    halt;
    end;

    procedure spfa;
    var head,tail,f:longint;
    begin
    head:=0; tail:=1; team[1]:=1; exist[1]:=true; dis[1]:=0;
    while head<tail do
    begin
    inc(head); head:=((head-1) mod 1001)+1;
    f:=h[team[head]]; exist[team[head]]:=false;
    while f<>0 do
    begin
    if dis[e[f].go]>dis[team[head]]+e[f].long then
    begin
    dis[e[f].go]:=dis[team[head]]+e[f].long;
    inc(change[e[f].go]); //important
    if change[e[f].go]>=2 then print; //important
    if not exist[e[f].go] then
    begin
    inc(tail); tail:=((tail-1) mod 1001)+1;
    team[tail]:=e[f].go;
    exist[e[f].go]:=true;
    end;
    end;
    f:=e[f].next;
    end;
    end;
    end;

    begin
    readln(n,m);
    for i:=1 to m do
    begin
    readln(x,y,z);
    ins(x,y,z);
    ins(y,x,-z);
    end;

    for i:=1 to n do
    begin
    exist[i]:=false;
    dis[i]:=maxlongint div 3;
    end;

    spfa;

    temp:=maxlongint;

    for i:=1 to n do
    if dis[i]<temp then
    begin
    temp:=dis[i];
    k:=i;
    end;

    for i:=1 to n do writeln(dis[i]-temp);
    end.

  • 0
    @ 2016-04-03 20:04:41

    想上为负,向下为正,bfs求1号珍珠到每个珍珠的距离(spfa也可以),找出最小距离,就是最上面的那颗珍珠,设其为k.
    那么其他珍珠i到珍珠k的距离为:d[i]-d[k]

  • 0
    @ 2015-03-17 15:39:57

    差分约束系统比较好写吧。。
    记得要建负权边。

  • 0
    @ 2013-10-04 16:49:42

    设f[i]表示i的位置
    定义f[x[1]]=5000
    那么f[x[2]]=f[X[1]]+l[1]
    然后每次找到其中有一个f知道的条件进行处理
    若找不到或矛盾则无解
    答案就是f[i]-min(f[i])

  • 0
    @ 2013-10-04 15:17:59

    想了半个小时,弱弱地用递推过了……
    var
    dis,mark,max,i,j,k,l,m,n,u:longint;
    map,a:array[0..500,0..500] of longint;
    h:array[0..10000] of longint;
    b:array[0..500] of boolean;
    bo:boolean;

    begin
    max:=-maxlongint;
    readln(n,m);
    for i:=1 to m do
    begin
    readln(l,k,u);
    map[l,k]:=u;
    map[k,l]:=-u;
    inc(a[l,0]);
    a[l,a[l,0]]:=k;
    inc(a[k,0]);
    a[k,a[k,0]]:=l;
    end;
    b[1]:=true;
    h[1]:=0;
    repeat
    bo:=true;
    for i:=1 to n do
    if b[i] then begin
    for j:=1 to a[i,0] do
    if not b[a[i,j]] then
    begin
    h[a[i,j]]:=h[i]-map[i,a[i,j]];
    b[a[i,j]]:=true;
    bo:=false;
    if h[a[i,j]]>max then
    begin
    mark:=a[i,j];
    max:=h[a[i,j]];
    end;
    end else
    begin
    l:=h[i]-map[i,a[i,j]];
    if h[a[i,j]]<>l then
    begin
    writeln('-1');
    halt;
    end;
    end;
    end;
    until bo;
    dis:=h[mark];
    for i:=1 to n do
    writeln(dis-h[i]);
    end.

    • @ 2013-10-05 10:16:16

      好棒啊 大神啊 加我为好友吧

  • 0
    @ 2012-10-25 12:32:52

    floyed 0.00s 全部秒过=-=

  • 0
    @ 2012-08-14 16:21:20

    明显是模拟啊。。。

    一次过。。

    说说无解的条件吧:

    1.p

  • 0
    @ 2010-03-12 21:08:02

    floyed能oms?怎么可能,最后一个点floyed应该会超时的

  • 0
    @ 2009-11-03 20:26:42

      用并查集的同学注意下,两点间构正边。

  • 0
    @ 2009-10-30 20:48:20

    通过 100人

    哈哈...庆祝一下...

    注意一个问题,就是在dfs时:

    if (h[a]

  • 0
    @ 2009-10-30 09:46:16

    bfs...就对付这数据了

    可是 请教大牛们 用并查集的话 要怎么做呢?或者说要合并两个集的时候怎么处理高度

  • 0
    @ 2009-10-28 20:06:54

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2009-10-05 21:55:41

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    膜拜雪牛!

信息

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