POJ 3660 传递闭包 warshall算法
scturtle
posted @ 2010年8月16日 19:31
in algorithm
, 1991 阅读
初始化为-1,计算传递闭包过程中赢记为1,输记为0,最后检查传递闭包中无-1的行数或列数。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int adj[101][101]; int tc[101][101]; int main() { //freopen("in.txt","r",stdin); int n,m,v,w,i,s,t,ans; scanf("%d%d",&n,&m); memset(adj,-1,sizeof(adj)); for(i=1; i<=n; i++) adj[i][i]=1; for(i=1; i<=m; i++) { scanf("%d%d",&v,&w); adj[v][w]=1; } for(s=1; s<=n; s++) for(t=1; t<=n; t++) tc[s][t]=adj[s][t]; for(i=1;i<=n;i++) for(s=1;s<=n;s++) if(tc[s][i]>0) for(t=1;t<=n;t++) if(tc[i][t]>0) {tc[s][t]=1;tc[t][s]=0;} // for(s=1; s<=n; s++) // { // for(t=1; t<=n; t++) // printf("%3d ",tc[s][t]); // cout<<endl; // } ans=n; for(s=1; s<=n; s++) for(t=1; t<=n; t++) if(tc[s][t]==-1) { ans--; break; } printf("%d\n",ans); return 0; }