Numbering Paths 统计任意两点间路的数量 小范围数据floyd变体
/*floyd的妙用啊。和倍增的思想有点类似。对哈希后的图矩阵作N次floyd后，图中任意两点的值表示两点之间路的条数。如果c[k][k]!=0，则说明k是环上一点。*/#include <stdio.h>#include <cstring>#include <iostream>using namespace std;int map[31][31];int main(){ int n,a,b,t; int ca=0; while(scanf("%d",&n)==1) { memset(map,0,sizeof(map)); t=0; for(int i=1;i<=n;i++) { scanf("%d%d",&a,&b); map[a][b]=1; t=max(t,max(a,b)); } for(int k=0;k<=t;k++) for(int i=0;i<=t;i++) for(int j=0;j<=t;j++) map[i][j]+=map[i][k]*map[k][j]; for(int k=0;k<=t;k++) { if(map[k][k]) { map[k][k]=-1; for(int i=0;i<=t;i++) for(int j=0;j<=t;j++) { if(map[i][k]&&map[k][j]) map[i][j]=-1; } } } printf("matrix for city %d\n",ca++); for(int i=0;i<=t;i++) for(int j=0;j<=t;j++) { if(j<t) printf("%d ",map[i][j]); else printf("%d\n",map[i][j]); } } return 0;}