首页 > 代码库 > Poj 2570 Fiber Network Floyd思想处理
Poj 2570 Fiber Network Floyd思想处理
感觉非常有意思,也不难想。
f[i][j] |= f[i][k] & f[k][j]
#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <stack>using namespace std;typedef long long LL;const int maxn = 205;int n,val[maxn][maxn];bool e[maxn][maxn];char buf[1024];int getval(char *s) { int len = strlen(s),ret = 0; for(int i = 0;i < len;i++) { ret |= (1 << (s[i] - ‘a‘)); } return ret;}void floyd() { for(int i = 1;i <= n;i++) { for(int j = 1;j <= n;j++) { for(int k = 1;k <= n;k++) { val[j][k] |= val[j][i] & val[i][k]; } } }}int main() { while(scanf("%d",&n),n) { memset(val,0,sizeof(val)); int a,b; while(scanf("%d%d",&a,&b),a) { scanf("%s",buf); val[a][b] = getval(buf) ; } floyd(); while(scanf("%d%d",&a,&b),a) { int cnt = 0; for(int i = 0;i < 26;i++) { if(val[a][b] & (1 << i)) { cnt++; putchar(i + ‘a‘); } } if(cnt == 0) putchar(‘-‘); puts(""); } puts(""); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。