Detail of message

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

帮我看看怎么处理TLE，代码如下

Posted by bmexue at 2006-10-12 15:31:39 on Problem 3035

#include <iostream>
#include <cmath>
using namespace std;
#define MAX 10

double RST[MAX];        //×&icirc;&ordm;ó&Oacute;&Atilde;&Agrave;&acute;&frac14;&Ccedil;&Acirc;&frac14;&Atilde;&iquest;&Icirc;&raquo;bits&Ecirc;&Ccedil;1&micro;&Auml;&cedil;&Aring;&Acirc;&Ecirc;
bool MAIT[1024][1024];  // &Aacute;&Uacute;&frac12;&Oacute;&frac34;&Oslash;&Otilde;ó&pound;&not;±í&Ecirc;&frac34;node&micro;&Auml;&Aacute;&acute;&frac12;&Oacute;&Ccedil;é&iquest;&ouml;
int FIR[1024];         // n&cedil;&ouml;&Ecirc;&yacute;&cedil;÷&Oacute;&ETH;&frac14;&cedil;&cedil;&ouml;±&szlig;&pound;¨&sup2;&raquo;&Ouml;&Oslash;&cedil;&acute;&pound;&copy;
double dp[101][1024]; //&frac14;&Ccedil;&Acirc;&frac14;&Atilde;&iquest;&Ograve;&raquo;&sup2;&frac12;&pound;&not;&sup2;ú&Eacute;ú0--1023&micro;&Auml;&cedil;&Aring;&Acirc;&Ecirc;
int k,n,e;

void init()
{
	memset(RST,0.0,sizeof(RST) );
	memset(MAIT, false, sizeof(MAIT) );
	memset(FIR, 0, sizeof(FIR) );
	memset (dp, 0.0 , sizeof(dp)); 

}
void make(int i) //&Aring;&ETH;&para;&Iuml;&Atilde;&iquest;&Ograve;&raquo;&sup2;&frac12;&sup2;ú&Eacute;ú&micro;&Auml;&Ecirc;&yacute;×&Ouml;&para;&Ocirc;n&micro;&Auml;&cedil;&Aring;&Acirc;&Ecirc;
{
   int ii=0;
   int tmp;
   int num = pow(2,n);
   for(int j=0;j<num;j++){ //&cedil;&ouml;&Ecirc;&yacute; 
         ii=0;
		 tmp=j;
		 while(true){
			 if(tmp%2 != 0)
				 RST[ii]= RST[ii]+ dp[i][j];
			 tmp = tmp>>1;
			 ii++;
			 if(tmp==0)
				 break;
		 }
	}
 
}
void doit()   //&frac12;&Uacute;&micro;&atilde;&Ecirc;&yacute;&Aacute;&iquest;pow(2,n),±à&ordm;&Aring;0,1,2,3,....,pow(2,n)-1;
{
    int i = 0;
	int num = pow(2,n);
	while( i< num ){
		dp[1][i] = 1.0/(double)num;
		i++;
	}
	int kk=2;
	int j;
    while(kk<=k){
		for(i=0; i< num ;i++){
		   for(j=0;j<num;j++){
			   if( MAIT[i][j] )
				   dp[kk][i] = dp[kk][i] + dp[kk-1][j] / (double)FIR[j];
		   }
		}
	   memset(RST,0.0,sizeof(RST) );
	   make(kk);
	   for(i=0;i<n;i++){
	     if( RST[i] >= 0.75 || RST[i]<=0.25){
			printf("No\n");
			return;
		 }
	   }
	  kk++;
	}
  
	printf("Yes\n");
}
int main()
{
	scanf("%d%d%d", &k,&n,&e);
	int ee;
	int v1,v2;
	while(k!=0)
	{
	  init();
      ee=0;
	  while(ee< e)
	  {
         scanf("%d%d", &v1,&v2);
		 if(!MAIT[v1][v2]){
            FIR[v1]++;
            FIR[v2]++;
		 }
		 MAIT[v1][v2] = true;
		 MAIT[v2][v1]  =true;
		 ee++;
	  }
     doit();
     scanf("%d%d%d", &k,&n,&e);
	}
	return 0;
}

Followed by:

Post your reply here:

User ID:
Password:
Title:

Content:

> #include <iostream>
> #include <cmath>
> using namespace std;
> #define MAX 10
> 
> double RST[MAX];        //×îºóÓÃÀ´¼ÇÂ¼Ã¿Î»bitsÊÇ1µÄ¸ÅÂÊ
> bool MAIT[1024][1024];  // ÁÚ½Ó¾ØÕó£¬±íÊ¾nodeµÄÁ´½ÓÇé¿ö
> int FIR[1024];         // n¸öÊý¸÷ÓÐ¼¸¸ö±ß£¨²»ÖØ¸´£©
> double dp[101][1024]; //¼ÇÂ¼Ã¿Ò»²½£¬²úÉú0--1023µÄ¸ÅÂÊ
> int k,n,e;
> 
> void init()
> {
> 	memset(RST,0.0,sizeof(RST) );
> 	memset(MAIT, false, sizeof(MAIT) );
> 	memset(FIR, 0, sizeof(FIR) );
> 	memset (dp, 0.0 , sizeof(dp)); 
> 
> }
> void make(int i) //ÅÐ¶ÏÃ¿Ò»²½²úÉúµÄÊý×Ö¶ÔnµÄ¸ÅÂÊ
> {
>    int ii=0;
>    int tmp;
>    int num = pow(2,n);
>    for(int j=0;j<num;j++){ //¸öÊý 
>          ii=0;
> 		 tmp=j;
> 		 while(true){
> 			 if(tmp%2 != 0)
> 				 RST[ii]= RST[ii]+ dp[i][j];
> 			 tmp = tmp>>1;
> 			 ii++;
> 			 if(tmp==0)
> 				 break;
> 		 }
> 	}
>  
> }
> void doit()   //½ÚµãÊýÁ¿pow(2,n),±àºÅ0,1,2,3,....,pow(2,n)-1;
> {
>     int i = 0;
> 	int num = pow(2,n);
> 	while( i< num ){
> 		dp[1][i] = 1.0/(double)num;
> 		i++;
> 	}
> 	int kk=2;
> 	int j;
>     while(kk<=k){
> 		for(i=0; i< num ;i++){
> 		   for(j=0;j<num;j++){
> 			   if( MAIT[i][j] )
> 				   dp[kk][i] = dp[kk][i] + dp[kk-1][j] / (double)FIR[j];
> 		   }
> 		}
> 	   memset(RST,0.0,sizeof(RST) );
> 	   make(kk);
> 	   for(i=0;i<n;i++){
> 	     if( RST[i] >= 0.75 || RST[i]<=0.25){
> 			printf("No\n");
> 			return;
> 		 }
> 	   }
> 	  kk++;
> 	}
>   
> 	printf("Yes\n");
> }
> int main()
> {
> 	scanf("%d%d%d", &k,&n,&e);
> 	int ee;
> 	int v1,v2;
> 	while(k!=0)
> 	{
> 	  init();
>       ee=0;
> 	  while(ee< e)
> 	  {
>          scanf("%d%d", &v1,&v2);
> 		 if(!MAIT[v1][v2]){
>             FIR[v1]++;
>             FIR[v2]++;
> 		 }
> 		 MAIT[v1][v2] = true;
> 		 MAIT[v2][v1]  =true;
> 		 ee++;
> 	  }
>      doit();
>      scanf("%d%d%d", &k,&n,&e);
> 	}
> 	return 0;
> }

Home Page Go Back To top