直接传递包~

这个题目开始用并查集做的。。效果不太好。。而且很容易头晕~

后来看到题目最大的点才200所以就用了类似图的传递包的算法

mp = 0 表示i与j关系不明确

mp = 1 表示i与j平行

mp = 2 表示i与j垂直

如果 i // k ,k // j (mp = 1 and mp[k,j] = 1) --> i // j (mp = 1) 如果此时发现mp = 2 那么就有error了~

如果 i 垂直 k ,k 垂直 j (mp = 2 and mp[k,j] = 2) --> i // j (mp = 1) 如果此时发现mp = 2 那么就有error了~

如果 i 垂直 k ,k // j (mp = 2 and mp[k,j] = 1) --> i 垂直 j (mp = 2) 如果此时发现mp = 1 那么就有error了~

如果 i // k ,k 垂直 j (mp = 1 and mp[k,j] = 2) --> i 垂直 j (mp = 2) 如果此时发现mp = 1 那么就有error了~

最后统计一下所有的 i < j 满足 mp = 1 一共有多少个就是Task1

对于Task2，每个mp输出相应的答案就可以了

更多就在：

http://hi.baidu.com/木子日匀/blog/item/9409b9c3253b1e3fe5dd3bdb.html

没说过给出的节点编号是连续的（不知道数据测试是不是这样），所以我开了个301×301×301的循环，很不好看地过了。

编译通过...

├ 测试数据 01：答案正确... 353ms

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

├ 测试数据 03：答案正确... 384ms

├ 测试数据 04：答案正确... 384ms

├ 测试数据 05：答案正确... 447ms

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

Accepted 有效得分：100 有效耗时：1568ms

___|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|_

具体方法详见传递闭包+位运算（floyd-warshall方法实现）。

传递闭包问题，用不用并查集都一样，只是并查集应该比flody快很多吧..还好数据不大~

不是吧,不用并查集的吧!

建图,每条线为一个顶点,若两线间平行则为这两点边权为0,否则为1,没有给出则为∞.

然后来一次floyd,若在floyd过程中发现(a+a[j,k]) and 1a and 1,就为矛盾情况.、

每个点之间的边权分别有三种情况:

1.a and 1=0(平行)

2.a and 1=1(垂直)

3.a=-1(未知)

然后根据询问再判断就ac了.

果然并差集，不过考试时只得了40！

巨汗..................做了一晚上40分................

我不会！！小胖的奇偶还没ac呢

编译通过...

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

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

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

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

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

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

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

一眼就看出是并查集

评测时只有20分吓死我了

.按食物连做的竟然WA了。

是不是有什么BUG

那个平行条数怎么算 NO IDEA 是算不算平行啊。

占楼~~orz....

靠，我才是第一个通过的！！！！！！！

脑残并查集...

mao2

岛儿的生日比赛第二题

我猜是数学题 平面几何？

板凳。

沙发

并查集AC……
program vj;

var ans,n,m,q,i,j,x,y,d:longint;
way,father:array[1..300] of longint;
t1,t2:longint;
ch,tip:char;

function getfather(k:longint):longint;
var tip:longint;
begin
if father[k]=k then exit(k);
tip:=father[k];
father[k]:=getfather(tip);
way[k]:=way[tip] xor way[k];
exit(father[k]);
end;

function getdata(a,b:longint):longint;
begin
getfather(a);
getfather(b);
exit(way[a] xor way[b]);
end;

procedure union(a,b,c:longint);
var k1,k2:longint;
begin
k1:=getfather(a);
k2:=getfather(b);
father[k1]:=k2;
way[k1]:=way[x] or c xor way[y];
end;

begin
//assign(input,'vj.in');
//assign(output,'vj.out');
//reset(input);
//rewrite(output);
readln(n,m,q);
for i:=1 to n do
begin
father[i]:=i;
way[i]:=0;
end;

for i:=1 to m do
begin
readln(ch,x,ch,tip,ch,ch,y);
t1:=getfather(x);
t2:=getfather(y);
if tip='p' then d:=0
else d:=1;
if t1<>t2 then union(x,y,d)
else if getdata(x,y)<>d then
begin
writeln('There must be something wrong...');
halt;
end;
end;
for i:=1 to n do
for j:=i+1 to n do
if (getfather(i)=getfather(j)) and (getdata(i,j)=0) then inc(ans);
writeln(ans);
for i:=1 to q do
begin
readln(ch,x,ch,ch,y);
if getfather(x)<>getfather(y) then writeln('No idea.')
else
begin
if getdata(x,y)=0 then writeln('Parallel.');
if getdata(x,y)=1 then writeln('Vertical.');
end;
end;
//close(input);
//close(output);
end.

并查集足够了，效率还高，只是我还没AC