首页 > 代码库 > POJ 3207 Ikki's Story IV - Panda's Trick
POJ 3207 Ikki's Story IV - Panda's Trick
简单的看了2-sat……似乎还是挺神奇的东西……等大致刷完几道题再来写总结吧!
而这道题……算是2-sat的超级入门题了吧
不过题目大意也是醉了:圆上顺序排列n个点,现要在一些点间连边,规定边只能在圆内或圆外,求有没有可能不相交 。一开始想的是嗷嗷嗷,圆上两个点的连线怎么可能有什么在圆外在圆内之分,不都是弦么?后来才知道……原来两个点的连线不是直线可以使曲线……
判定是否相交很简单吧……看成是一条直线上四个点,那么如果e1.a<e2.a<e1.b<e2.b就相交啦……
都说是热身题没多难……
type arr1=record a,b:longint; end; arr2=record toward,next:longint; end;var e:array[0..3000]of arr1; edge:array[0..3000]of arr2; first,dfn,low,scc,p,num1,num2:array[0..3000]of longint; chose:array[0..3000]of boolean; time,total,tot,n,m,tail,sum:longint;procedure swap(var x,y:longint);var i:longint;begin i:=x; x:=y; y:=i;end;procedure addedge(j,k:longint);begin inc(total); edge[total].toward:=k; edge[total].next:=first[j]; first[j]:=total;end;procedure add(j,k:longint);begin addedge(j,k); addedge(k,j);end;function check(x,y:arr1):boolean;begin if (x.a<y.a) and (y.a<x.b) and (x.b<y.b) then exit(true); exit(false);end;procedure tarjan(x:longint);var i,too,j:longint;begin inc(time); dfn[x]:=time; low[x]:=time; chose[x]:=true; inc(tail); p[tail]:=x; i:=first[x]; while i>0 do begin too:=edge[i].toward; if dfn[too]=0 then begin tarjan(too); if low[too]<low[x] then low[x]:=low[too]; end else if dfn[too]<low[x] then low[x]:=dfn[too]; i:=edge[i].next; end; if dfn[x]=low[x] then begin inc(sum); repeat j:=p[tail]; dec(tail); chose[j]:=false; scc[j]:=sum; until j=x; end;end;procedure into;var i,j:longint;begin readln(n,m); for i:=1 to m do begin read(e[i].a,e[i].b); if e[i].a>e[i].b then swap(e[i].a,e[i].b); inc(tot); num1[i]:=tot; inc(tot); num2[i]:=tot; end; for i:=1 to m-1 do for j:=i+1 to m do if check(e[i],e[j]) or check(e[j],e[i]) then begin add(num1[i],num2[j]); add(num2[i],num1[j]); end;end;function work:boolean;var i:longint;begin for i:=1 to tot do if dfn[i]=0 then tarjan(i); for i:=1 to m do if scc[num1[i]]=scc[num2[i]] then exit(false); exit(true);end;begin into; if work then writeln(‘panda is telling the truth...‘) else writeln(‘the evil panda is lying again‘);end.
POJ 3207 Ikki's Story IV - Panda's Trick
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。