Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

floyd过的,原来这玩意也可以用邻接表。

Posted by alpc32 at 2009-09-03 17:03:01 on Problem 3275 and last updated at 2009-09-03 17:04:07
/* designed by alpc32 from NUDT */
#include <iostream>
using namespace std;

int n,m;
int big[1005][1005];
int sma[1005][1005];
bool rel[1005][1005];

int main()
{
      int i,j,k;
	  int a,b;

	  scanf("%d%d",&n,&m);
	  memset(sma,0,sizeof(sma));
	  memset(big,0,sizeof(big));
	  memset(rel,0,sizeof(rel));
      for(i=0;i<m;i++){
		  scanf("%d%d",&a,&b);
		  big[a][++big[a][0]]=b;
		  sma[b][++sma[b][0]]=a;
	      rel[a][b]=1;
	  }

	  for(k=1;k<=n;k++){
		  for(i=1;i<=sma[k][0];i++){
			  a=sma[k][i];
			  for(j=1;j<=big[k][0];j++){
				  b=big[k][j];
				  if(!rel[a][b]){
				  big[a][++big[a][0]]=b;
				  sma[b][++sma[b][0]]=a;
				  rel[a][b]=1;
				  }
			  }
		  }
	  }
     
	int ans=0;
	 for(i=1;i<=n;i++)
		 ans+=sma[i][0]+big[i][0];
     ans=n*(n-1)/2-ans/2;
	 printf("%d\n",ans);
     return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator