ZOJ 1589 Professor John ~Floyd算法
这题用Floyd和Dij都可以,但是感觉用Floyd会十分方便,也是第一次使用Floyd算法,一开始没有这个思路滴,参考别人的。。~~~~(>_<)~~~~
#include<stdio.h> #include<iostream> #include<string.h> using namespace std; int main(void) { int ncases,n,i,j,k; int map[30][30],mark[30][30]; cin>>ncases; for(int f = 1;f<=ncases;f++) { memset(map,0,sizeof(map)); memset(mark,0,sizeof(mark)); int flag = 1; cin>>n; char s[4]; while(n--) { scanf("%s",s); int a,b; char o; a = s[0]- 'A' + 1; o = s[1]; b = s[2]- 'A' + 1; if(o=='<') map[a][b] = 1; else map[b][a] = 1; } memcpy(mark,map,sizeof(map)); for(k = 1;k<=28;k++) for(i = 1;i<=28;i++) for(j =1;j<=28;j++) map[i][j] = map[i][j]||(map[i][k]&&map[k][j]);//这里很巧妙地将Floyd做了变形。。至少我这个弱菜是这么认为的,啊哈 printf("Case %d:\n",f); for(i = 1;i<=28;i++) for(j =1;j<=28;j++) if((map[i][j])&&!mark[i][j]) { printf("%c<%c\n",i+'A'-1,j+'A'-1); flag = 0; } if(flag) printf("NONE\n"); } return 0; }
补充:软件开发 , C++ ,