bzoj2788

明显是一个差分约束系统

对于第一种限制，其实就是x[a]+1<=x[b] x[b]-1<=x[a]

根据三角不等式很容易建图

但这题他比较奇怪，问的是X最多不同取值的个数

根据这张图的特殊性我们不难发现，两个强联通分量内X的取值种类是互不干涉的

也就是说我们可以分别统计每个强联通分量然后累计即可

为什么这样呢？观察这个限制，两个强联通分量之间只可能存在第二种限制的单向边，xc<=xd 显然xc,xd可以取不同取值

怎么统计强联通分量内的答案呢？

首先对于差分约束系统的可行解是最长路，每块的答案就是点与点之间距离绝对值的最大值

注意无解就是存在正环

  1 const inf=1000000007;
  2 type node=record
  3        po,next:longint;
  4      end;
  5 
  6 var e:array[0..300010] of node;
  7     st,q,p,dfn,low:array[0..610] of longint;
  8     d:array[0..610,0..610] of longint;
  9     v,f:array[0..610] of boolean;
 10     h,s,ans,x,y,len,j,t,i,n,m1,m2:longint;
 11 
 12 procedure max(var a:longint;b:longint);
 13   begin
 14     if b>a then a:=b;
 15   end;
 16 
 17 function min(a,b:longint):longint;
 18   begin
 19     if a>b then exit(b) else exit(a);
 20   end;
 21 
 22 procedure add(x,y:longint);
 23   begin
 24     inc(len);
 25     e[len].po:=y;
 26     e[len].next:=p[x];
 27     p[x]:=len;
 28   end;
 29 
 30 procedure floyd;
 31   var i,j,k:longint;
 32   begin
 33     for k:=1 to s do
 34       for i:=1 to s do
 35         if d[q[i],q[k]]>-inf then
 36           for j:=1 to s do
 37             if d[q[k],q[j]]>-inf then
 38               max(d[q[i],q[j]],d[q[i],q[k]]+d[q[k],q[j]]);
 39     for i:=1 to s do
 40       if d[q[i],q[i]]>0 then
 41       begin
 42         writeln('NIE');
 43         halt;
 44       end;
 45 
 46     k:=0;
 47     for i:=1 to s do
 48       for j:=1 to s do
 49         if d[q[i],q[j]]>-inf then max(k,abs(d[q[i],q[j]]));
 50     ans:=ans+k+1;
 51   end;
 52 
 53 procedure dfs(x:longint);
 54   var i,y:longint;
 55   begin
 56     inc(h);
 57     dfn[x]:=h;
 58     low[x]:=h;
 59     v[x]:=true;
 60     inc(t);
 61     st[t]:=x;
 62     f[x]:=true;
 63     i:=p[x];
 64     while i<>0 do
 65     begin
 66       y:=e[i].po;
 67       if not v[y] then
 68       begin
 69         dfs(y);
 70         low[x]:=min(low[x],low[y]);
 71       end
 72       else if f[y] then low[x]:=min(low[x],low[y]);
 73       i:=e[i].next;
 74     end;
 75     if dfn[x]=low[x] then
 76     begin
 77       s:=0;
 78       while st[t+1]<>x do
 79       begin
 80         inc(s);
 81         q[s]:=st[t];
 82         f[st[t]]:=false;
 83         dec(t);
 84       end;
 85       floyd;
 86     end;
 87   end;
 88 
 89 begin
 90   readln(n,m1,m2);
 91   for i:=1 to n do
 92     for j:=1 to n do
 93       if i<>j then d[i,j]:=-inf;
 94   for i:=1 to m1 do
 95   begin
 96     readln(x,y);
 97     add(x,y);
 98     add(y,x);
 99     max(d[x,y],1);
100     max(d[y,x],-1);
101   end;
102   for i:=1 to m2 do
103   begin
104     readln(x,y);
105     add(x,y);
106     max(d[x,y],0);
107   end;
108   for i:=1 to n do
109     if not v[i] then
110     begin
111       h:=0;
112       t:=0;
113       dfs(i);
114     end;
115 
116   writeln(ans);
117 end.

View Code