注: 这道题和 poj1182 食物链很像.
AC 代码如下：

#include <iostream>
#include <cctype>
using namespace std;

const int maxn = 410;
int father[maxn];

int find(int x) {
    if (x == father[x])
        return x;
    else
        return father[x] = find(father[x]);
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    father[x] = y;
}

int main() {
    ios::sync_with_stdio(false);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= 2 * n; i++)
        father[i] = i;
    while (m--) {
        string s;
        cin >> s;
        int num1 = s[1] - '0';
        if (isdigit(s[2])) num1 = num1 * 10 + s[2] - '0';
        if (isdigit(s[3])) num1 = num1 * 10 + s[3] - '0';
        char ch;
        cin >> ch;
        cin >> s;
        int num2 = s[1] - '0';
        if (isdigit(s[2])) num2 = num2 * 10 + s[2] - '0';
        if (isdigit(s[3])) num2 = num2 * 10 + s[3] - '0';
        if (ch == 'p') {
            if (find(num1) == find(num2 + n)) {
                cout << "There must be something wrong..." << endl;
                return 0;
            }
            unite(num1, num2);
            unite(num1 + n, num2 + n);
        } else {
            if (find(num1) == find(num2)) {
                cout << "There must be something wrong..." << endl;
                return 0;
            }
            unite(num1, num2 + n);
            unite(num1 + n, num2);
        }
    }
    int _count = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            if (find(i) == find(j) || find(i + n) == find(j + n))
                _count++;
    cout << _count << endl;
    while (q--) {
        string s;
        cin >> s;
        int num1 = s[1] - '0';
        if (isdigit(s[2])) num1 = num1 * 10 + s[2] - '0';
        if (isdigit(s[3])) num1 = num1 * 10 + s[3] - '0';
        cin >> s;
        int num2 = s[1] - '0';
        if (isdigit(s[2])) num2 = num2 * 10 + s[2] - '0';
        if (isdigit(s[3])) num2 = num2 * 10 + s[3] - '0';
        if (find(num1) == find(num2) || find(num1 + n) == find(num2 + n))
            cout << "Parallel." << endl;
        else if (find(num1) == find(num2 + n) || find(num1 + n) == find(num2))
            cout << "Vertical." << endl;
        else
            cout << "No idea." << endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 200, M = 401;
int fa[M], sum[M], ans;
bool v[N + 1];
int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void u(int x, int y) {
        sum[fa[x]] += sum[find(y)];
        fa[find(y)] = fa[x];
}
int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int n, m, p;
        cin >> n >> m >> p;
        for (int i = 1; i <= N; i++)
                sum[i] = 1;
        for (int i = 1; i <= M; i++)
                fa[i] = i;
        for (int i = 1; i <= m; i++) {
                int x, y;
                char a, c;
                cin >> a >> x >> c >> a >> y;
                if (c == 'p')
                        u(x, y), u(x + N, y + N);
                else
                        u(x + N, y), u(x, y + N);
        }
        for (int i = 1; i <= n; i++) {
                if (fa[i] == fa[i + N]) {
                        cout << "There must be something wrong...";
                        return 0;
                }
                if (!v[find(i)]) {
                        ans += sum[fa[i]] * (sum[fa[i]] - 1) / 2;
                        v[fa[i]] = 1;
                }
        }
        cout << ans << '\n';
        for (int i = 1; i <= p; i++) {
                int x, y;
                char a;
                cin >> a >> x >> a >> y;
                if (fa[x] == fa[y])
                        cout << "Parallel." << '\n';
                else if (fa[x] == fa[y + N])
                        cout << "Vertical." << '\n';
                else
                        cout << "No idea." << '\n';
        }
        return 0;
}

#include<iostream>
#include<cstring>
using namespace std;

int n, m, q;
int g[201][201];
bool visited[201][201];
int s, ans = 0;
void dfs(int ahead, int i) {
int j;
if (g[s][i] == 0 && ahead != i && ahead != s && i != s) {
if ((g[s][ahead] == 1 && g[ahead][i] == 1) || (g[s][ahead] == 2 && g[ahead][i] == 2)) {
g[s][i] = 1;
g[i][s] = 1;
}
else {
g[s][i] = 2; g[i][s] = 2;
}
}
for (j = 1; j <= n; j++) {
if (g[i][j] > 0 && !visited[i][j]) {
visited[i][j] = true;
visited[j][i] = true;
dfs(i, j);
}
}
}
int main() {
memset(g, 0, sizeof(g));
cin >> n >> m >> q;
for (int i = 0; i < m; i++) {
char c, state;
int l1, l2;
cin >> c >> l1 >> state >> c >> l2;
if (state == 'p') {
if (g[l1][l2] != 0) {
cout << "There must be something wrong..." << endl;
return 0;
}
g[l1][l2] = 1; g[l2][l1] = 1;
}
else {
g[l1][l2] = 2;
g[l2][l1] = 2;
}
}
for (int i = 1; i <= n; i++) {
memset(visited, false, sizeof(visited));
s = i;
dfs(s, s);
}

for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if (g[i][j] == 1) ans++;
}
}

cout << ans << endl;
char c;
int l1, l2;
for (int i = 0; i < q; i++) {
cin >> c >> l1 >> c >> l2;
if (g[l1][l2] == 0) cout << "No idea." << endl;
else if (g[l1][l2] == 1) cout << "Parallel." << endl;
else cout << "Vertical." << endl;
}
return 0;
}

？？？
BF题解在这。。。
题解

良心题解
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,q,f[410],ans(0);
int used[210];
bool p(0);
char s;
struct p
{
int x,y,z;
}e[1005];
int find(int x)
{
if(f[x]==x)return x;
return find(f[x]);
}
void UN(int x,int y)
{
int a=find(x);
int b=find(y);
f[a]=b;
}
int main()
{
scanf("%d %d %d\n",&n,&m,&q);
for(int i=1;i<=2*n;i++)
f[i]=i;
for(int i=1;i<=m;i++)
{
getchar();
scanf("%d",&e[i].x);
getchar();
s=getchar();
getchar();
getchar();
scanf("%d",&e[i].y);
if(s=='p')
{
if(find(e[i].x)!=find(e[i].y+n)&&find(e[i].y)!=find(e[i].x+n))
{
UN(e[i].x,e[i].y);
UN(e[i].x+n,e[i].y+n);
}
else
{
printf("There must be something wrong...\n");
p=1;
break;
}
}
else
if(s=='v')
{
if(find(e[i].x)!=find(e[i].y)&&find(e[i].x+n)!=find(e[i].y+n))
{
UN(e[i].x,e[i].y+n);
UN(e[i].y,e[i].x+n);
}
else
{
printf("There must be something wrong...\n");
p=1;
break;
}
}
getchar();
}
if(p==0)
{
for(int i=1;i<=n-1;i++)
{
for(int j=i+1;j<=n;j++)
{
if(find(i)==find(j)&&used[j]==0)
{
used[j]=1;
// printf("%d %d\n",i,j);
ans++;
}
if(find(i)==find(j+n))
{
for(int o=j+1;o<=n;o++)
{
if(find(o)==find(j+n)&&used[o]==0)
{
used[o]=1;
// printf("%d %d %d\n",i,j,o);
ans++;
}
}
}
}
memset(used,0,sizeof(used));
}
}
//printf("-----------------\n");
if(p==0)
printf("%d\n",ans);
if(p==0)
{
for(int i=1;i<=q;i++)
{
int x,y;
getchar();
scanf("%d",&x);
getchar();
getchar();
scanf("%d",&y);
getchar();
if(find(x)==find(y))
printf("Parallel.\n");
else
if(find(x)==find(y+n))
printf("Vertical.\n");
else
printf("No idea.\n");
}
}
return 0;
}

回:voyagec2

原来是L1,L2,不是11,12 ...

嗯？什么情况..应该小写才对..

P1697平面几何
Accepted

记录信息

评测状态 Accepted
题目 P1697 平面几何
递交时间 2015-07-01 10:44:11
代码语言 C++
评测机 VijosEx
消耗时间 46 ms
消耗内存 284 KiB
评测时间 2015-07-01 10:44:13

评测结果

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 280 KiB, score = 20

测试数据 #1: Accepted, time = 0 ms, mem = 280 KiB, score = 20

测试数据 #2: Accepted, time = 0 ms, mem = 284 KiB, score = 20

测试数据 #3: Accepted, time = 15 ms, mem = 280 KiB, score = 20

测试数据 #4: Accepted, time = 31 ms, mem = 284 KiB, score = 20

Accepted, time = 46 ms, mem = 284 KiB, score = 100

代码

#include <iostream>
#include <stdio.h>

using namespace std;

int n , m , q;
int i , j , k;
char s[1000];
int x , y;
int ans;
int pre[ 200 + 10 ];
int cond[ 200 + 10 ];
int e;
char st;

int find( int x )
{
if( x == pre[x] )
return x;
return find( pre[x] );
}

int sta( int x )
{
int st = 1;
while( x != pre[x] )
{
st *= cond[x];
x = pre[x];
}
st *= cond[x];
return st;
}

void merge( int x , int y, int st )
{
int t = find( x );
cond[ t ] = sta( x ) * st;
pre[ t ] = y;
return;
}

int main()
{
scanf( "%d %d %d" , &n , &m , &q );
for( i = 1 ; i <= n ; i++ )
{
pre[i] = i;
cond[i] = 1;
}
getchar();
for( i = 0 ; i < m ; i++ )
{
x = y = 0;

cin >> s;
for( k = 1 ; s[k] != 0 && s[k] != '\0' ; k++ )
{
x *= 10;
x += s[k] - '0';
}

cin >> s;
st = s[0];
cin >> s;
for( k = 1 ; s[k] != 0 && s[k] != '\0' ; k++ )
{
y *= 10;
y += s[k] - '0';
}
if( st == 'p' )
{
if( find( x ) != find( y ) )
merge( x , y , 1 );
else if( sta( x ) == sta( y ) )
;
else
{
printf( "There must be something wrong...\n" );
return 0;
}
}
else
{
if( find( x ) != find( y ) )
merge( x , y , -1 );
else if( sta( x ) == -sta( y ) )
;
else
{
printf( "There must be something wrong...\n" );
return 0;
}
}
}
for( i = 1 ; i <= n ; i++ )
for( j = i + 1 ; j <= n ; j++ )
if( find( i ) == find( j ) && sta( i ) == sta( j ) )
ans++;
cout << ans << endl;
for( i = 0 ; i < q ; i++ )
{
scanf( "%s" , s );
x = y = 0;
for( k = 1 ; s[k] != 0 && s[k] != '\0' ; k++ )
{
x *= 10;
x += s[k] - '0';
}
scanf( "%s" , s );
for( k = 1 ; s[k] != 0 && s[k] != '\0' ; k++ )
{
y *= 10;
y += s[k] - '0';
}
if( find( x ) == find( y ) )
{
e = sta( x ) * sta( y );
if( e > 0 )
printf( "Parallel.\n" );
else
printf( "Vertical.\n" );
}
else
printf( "No idea.\n" );
}
//system( "pause" );
return 0;
}

评测结果
编译成功

foo.cpp: In function 'int main()':
foo.cpp:9:10: warning: unused variable 'l2' [-Wunused-variable]
char l1,l2,l3,l4,ch;
^
测试数据 #0: Accepted, time = 0 ms, mem = 684 KiB, score = 20
测试数据 #1: Accepted, time = 0 ms, mem = 688 KiB, score = 20
测试数据 #2: Accepted, time = 0 ms, mem = 688 KiB, score = 20
测试数据 #3: Accepted, time = 0 ms, mem = 688 KiB, score = 20
测试数据 #4: Accepted, time = 62 ms, mem = 684 KiB, score = 20
Accepted, time = 62 ms, mem = 688 KiB, score = 100
代码
#include<iostream>
#include<cstdio>
using namespace std;
int a[210][210];
int n,m,t;
int main()
{
cin>>n>>m>>t;
char l1,l2,l3,l4,ch;
int x,y,num;
for(int i=1;i<=n;i++)
a[i][i]=1;
for(int i=1;i<=m;i++)
{
cin>>l1>>x>>ch>>l4>>y;
num=a[x][y];
if(ch=='p')
{
a[x][y]=1;
a[y][x]=1;
}
if(ch=='v')
{
a[x][y]=-1;
a[y][x]=-1;
}
if(num+a[x][y]==0)
{
cout<<"There must be something wrong..."<<endl;
return 0;
}
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
num=a[i][j];
if((a[i][k]!=0)&&(a[j][k]!=0))
a[i][j]=a[i][k]*a[j][k];
a[j][i]=a[i][j];
if((num!=0)&&(a[i][j]!=num))
{
cout<<"There must be something wrong..."<<endl;
return 0;
}
}
num=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if((a[i][j]==1)&&(i!=j)) num++;
cout<<num/2<<endl;
for(int i=1;i<=t;i++)
{
cin>>l1>>x>>l3>>y;
if(a[x][y]==-1) cout<<"Vertical."<<endl;
if(a[x][y]==1) cout<<"Parallel."<<endl;
if(a[x][y]==0) cout<<"No idea."<<endl;
}
return 0;
}

测试数据 #0: Accepted, time = 0 ms, mem = 892 KiB, score = 20
测试数据 #1: Accepted, time = 0 ms, mem = 888 KiB, score = 20
测试数据 #2: Accepted, time = 0 ms, mem = 892 KiB, score = 20
测试数据 #3: Accepted, time = 0 ms, mem = 888 KiB, score = 20
测试数据 #4: Accepted, time = 0 ms, mem = 888 KiB, score = 20
Accepted, time = 0 ms, mem = 892 KiB, score = 100

秒杀。
program p1697;
var a,b,c,d:array[0..10000] of longint;
n,m,p,sum:longint;
//
procedure init;
var i:longint;
begin
readln(n,m,p);
end;
//
function fa(p:longint):longint;
var p1,p2,p3,p4,p5:longint;
begin
p1:=p;p2:=p;p3:=0;
while p1<>a[p1] do
begin
p3:=p3+b[p1];p1:=a[p1];
end;
while p2<>p1 do
begin
p4:=a[p2];a[p2]:=p1;p5:=b[p2];b[p2]:=p3;
p3:=p3-p5;p2:=p4;
end;
exit(p1);
end;
//
procedure main;
var i,p1,p2,p3,h1,h2:longint;
c:char;
begin
for i:=1 to n do a[i]:=i;
for i:=1 to m do
begin
read(c);read(p1);read(c);read(c);
if c='p' then p3:=0
else p3:=1;
read(c);read(c);readln(p2);
h1:=fa(p1);h2:=fa(p2);
if h1=h2 then
if (abs((b[p1] mod 2)-(b[p2] mod 2)) mod 2)<>p3 then
begin
write('There must be something wrong...');
close(output);halt;
end;
if h1<>h2 then
begin
a[h1]:=h2;b[h1]:=((b[p1]+p3-b[p2]) mod 2+2) mod 2;
end;
end;
end;
//
procedure print;
var i,h,h1,h2,p1,p2:longint;
cc:char;
begin
for i:=1 to n do
begin
h:=fa(i);
if b[i] mod 2=0 then inc(c[h])
else inc(d[h]);
end;
for i:=1 to n do sum:=sum+((c[i]*(c[i]-1)) div 2)+((d[i]*(d[i]-1)) div 2);
writeln(sum);
for i:=1 to p do
begin
read(cc);read(p1);read(cc);read(cc);readln(p2);
h1:=fa(p1);h2:=fa(p2);
if h1=h2 then
begin
if (abs(b[p1]-b[p2]) mod 2+2) mod 2=1 then writeln('Vertical.')
else writeln('Parallel.');
end
else writeln('No idea.');
end;
end;
//
begin
init;
main;
print;
end.

var x,y,n,m,i,j,q,s,k:longint;

c,cc:char;

a:array [0..200,0..200] of longint;

begin

assign(input,'geometry.in');reset(input);

assign(output,'geometry.out');rewrite(output);

readln(n,m,q);

for i:=1 to m do

begin

readln(c,x,c,cc,c,c,y);

if a[x,y]>0 then

begin

writeln('There must be something wrong...');

close(input);close(output);

halt;

end;

if cc='p' then a[x,y]:=1 else a[x,y]:=2;

a[y,x]:=a[x,y];

end;

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

if (ij) and (ik) and (kj) and (a=0)

and (a>0) and (a[k,j]>0) then

begin

if a=a[k,j] then a:=1

else a:=2;

a[j,i]:=a;

end;

for i:=1 to n-1 do

for j:=i+1 to n do

if a=1 then inc(s);

writeln(s);

for i:=1 to q do

begin

readln(c,x,c,c,y);

if a[x,y]=1 then writeln('Parallel.');

if a[x,y]=2 then writeln('Vertical.');

if a[x,y]=0 then writeln('No idea.');

end;

close(input);close(output);

end.

没人在哇 都是09年11月的留言

编译通过...

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

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

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

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

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

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

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

写了并查集，效率很高。。

其实这一道题目是食物链的弱化版，只要用加权的并查集就能秒杀。。。

还有就是细节处理要注意，特别是读入数据的部分，有点不爽！！！

幸好一次AC

感慨啊！这题终于过了啊！

先用并查集，调了n次，信心丧失。

后来改变算法，用floyd的传递闭包，终于过了！

好开心！！！

Flag Unaccepted

题号 P1697

类型(？) 其他

通过 250人

提交 682

通过率 37%

明明知道可以floyed（代碼60+），結果無聊寫了一個并查集（代碼100+），

結果調了N久，以後還是要KISS啊！

Floyed 真正有用的部分…………

说实话预处理比较烦，直接给不就行了，还得在前面加个字母…………

bool long_link(int k)

{int i,j;

int tmp;

for(i=1;i

'哎呀...测试数据都是很善意的...我们没有刻意要害大家...'

那么就不应该有第二组数据！！！

感谢HeavenSea，不然还真想不到这么贱的数据

Floyd's Algorithm

或者类似于

PKU ACM 1182 食物链 的算法

谁有第四组数据，这组我总错