Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
矩阵乘法思想咋不对(数据也过了)???就是很模拟的算法#include<iostream> #include<cstring> using namespace std; const int N=102; int map[N][N],tmap[N][N]; void warshell(int n) { int i,j,k; for(i=1;i<=n;++i) for(j=1;j<=n;++j) { for(k=1;k<=n;++k) tmap[i][j]=tmap[i][j] || (map[i][k] && map[k][j]); tmap[i][j]=(map[i][j] || tmap[i][j]); } } int main() { int n,i,j,k,m; memset(map,0,sizeof(map)); memset(tmap,0,sizeof(tmap)); scanf("%d%d",&n,&m); for(i=0;i<m;++i) { scanf("%d%d",&j,&k); map[j][k]=1; } warshell(n); int ans=0,tmp; for(i=1;i<=n;++i) { tmp=0; for(j=1;j<=n;++j) if(i!=j) if(tmap[i][j] || tmap[j][i]) ++tmp; if(tmp==n-1) ++ans; } printf("%d\n",ans); return false; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator