定義一個二維數組d[i][j]，d[i][j]==0表示i和j的關系不明確，d[i][j]==1表示i和j平行，d[i][j]==2表示i和j垂直。這樣的話就可以像Floyed一樣遞推，具體遞推方式請看代碼，寫得很清楚。
以下是我的代碼：
#include<stdio.h>
#define MAXN 208
int main()
{
long n,m,p,d[MAXN][MAXN]={0};
long i,j,k,a,b,tmp,ans;
char ch,wrong[]="There must be something wrong";
char s1[]="Parallel.",s2[]="Vertical.",s3[]="No idea.";
scanf("%ld%ld%ld\n",&n,&m,&p);
for(i=1;i<=m;i++)
{
getchar();
scanf("%ld",&a);getchar();
ch=getchar();getchar();getchar();
scanf("%ld\n",&b);
if(ch=='p')
{
if(d[a][b]==2||d[b][a]==2)
{
printf("%s\n",wrong);
return;
}
d[a][b]=d[b][a]=1;
}
else if(ch=='v')
{
if(d[a][b]==1||d[b][a]==1)
{
printf("%s\n",wrong);
return;
}
d[a][b]=d[b][a]=2;
}
}
// Read In
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(k!=i&&i!=j&&j!=k)
{
tmp=d[i][j];
if(d[i][k]==1&&d[k][j]==1)
d[i][j]=d[j][i]=1;
else if(d[i][k]==2&&d[k][j]==2)
d[i][j]=d[j][i]=1;
else if((d[i][k]==1&&d[k][j]==2)||(d[i][k]==2&&d[k][j]==1))
d[i][j]=d[j][i]=2;
if((tmp==1&&d[i][j]==2)||(tmp==2&&d[i][j]==1))
{
printf("%s\n",wrong);
return;
}
}
ans=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(d[i][j]==1)
ans++;
printf("%ld\n",ans/2);
for(i=1;i<=p;i++)
{
getchar();scanf("%ld",&a);
getchar();getchar();
scanf("%ld\n",&b);
if(d[a][b]==1)
printf("%s\n",s1);
else if(d[a][b]==2)
printf("%s\n",s2);
else if(d[a][b]==0)
printf("%s\n",s3);
}
return 0;
}
posted on 2010-01-06 20:28
lee1r 閱讀(178)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃