TOJ----1037---最大独立集

自即日起每天好好做2 3题....

今天想开个好头的然后悲剧的TLE。。。

先上题

touch me

嗯.... 无言分析在我的代码注释中给出了

我写了 2种分别是二维数组与 vector

一开始以为二维数组超时然后 vector可以过

事实无情地告诉我太天真了。。。

现在仍旧 TLE中应该可以在明天解决吧先纪念下我的TLE代码

 1 // 二分图 --- 最大独立集
 2 // 先使用了 mp 二维数组来实现 超时 
 3 // 然后用了vector存储 还是 tle ..........
 4 
 5 #include <iostream>
 6 #include <cstring>
 7 #include <vector>
 8 using namespace std;
 9 
10 const int size = 520;
11 struct data
12 {
13     int height;
14     char gendle;
15     char music[110];
16     char sport[110];
17 }couple[size];
18 bool vis[size];
19 int linker[size];
20 // bool mp[size][size];
21 vector<int>ve[size]; 
22 int n;
23 
24 bool judge( data p , data q ) // 判断能否连接起来 将不满足老师4个条件的2个学生连接起来
25 {
26     if( ( (p.height-q.height<=-40) || (p.height-q.height>=40) ) || p.gendle==q.gendle || strcmp( p.music,q.music) || !strcmp(p.sport,q.sport) )
27         return false; // false 不连接
28     return true;   
29 }
30 
31 bool dfs( int v )
32 {
33     for( int u = 0 ; u<ve[v].size() ; u++ )
34     {
35         if( !vis[ ve[v][u] ]  )
36         {
37             vis[ ve[v][u] ] = true;
38             if( linker[ ve[v][u] ]==-1 || dfs( linker[ ve[v][u] ] ) )
39             {
40                 linker[ ve[v][u] ] = v;
41                 return true;
42             }
43         }
44     }
45     return false;
46 }
47 
48 int maxMatch()
49 {
50     int cnt = 0;
51     memset( linker , -1 , sizeof(linker) );
52     for( int u = 0 ; u<n ; u++ )
53     {
54         memset( vis , false , sizeof(vis) );
55         if( ve[u].size()!=0 && dfs(u) )
56             cnt++;
57     }
58     return cnt;
59 }
60 
61 int main()
62 {
63     int t , i , j;
64     scanf( "%d",&t );
65     while( t-- )
66     {
67         scanf( "%d",&n );
68         for( i = 0 ; i<size ; i++ )
69             ve[i].clear();
70         //memset( mp , false , sizeof(mp) );
71         for( i = 0 ; i<n ; i++ )
72         {
73             scanf( "%d %c %s %s",&couple[i].height,&couple[i].gendle,couple[i].music,couple[i].sport );
74         }
75         for( i = 0 ; i<n ; i++ )
76         {
77             for( j = i+1 ; j<n ; j++ )
78             {
79                 if( judge(couple[i],couple[j]) )
80                 {
81                     ve[i].push_back(j);
82                 }
83             }
84         }
85         printf( "%d
", n-maxMatch() );
86     }
87     return 0;
88 }

View Code

嗯 1点钟已经到了在TZ还是 TLE 肯定是写法太挫了然后我去POJ 交了先WA 然后我换了种方法 1000+ms ac 怪不得在TZ 是 TLE

但是i 还没搞懂为什么 WA呢

  1 // 二分图 --- 最大独立集
  2 // 先使用了 mp 二维数组来实现 超时 
  3 // 然后用了vector存储 还是 tle ..........
  4 
  5 #include <iostream>
  6 #include <cstring>
  7 #include <vector>
  8 #include <cstdio>
  9 using namespace std;
 10 
 11 const int size = 520;
 12 struct data
 13 {
 14     int height;
 15     char gendle;
 16     char music[110];
 17     char sport[110];
 18 }couple[size];
 19 bool vis[size];
 20 int linker[size];
 21 // bool mp[size][size];
 22 vector<int>ve[size]; 
 23 int n;
 24 
 25 bool judge( data p , data q ) // 判断能否连接起来 将不满足老师4个条件的即会发生恋爱关系的学生 连接起来
 26 {
 27     if( ( (p.height-q.height<-40) || (p.height-q.height>40) ) || p.gendle==q.gendle || strcmp( p.music,q.music)!=0 || !strcmp(p.sport,q.sport) )
 28         return false; // false 不连接
 29     return true;   
 30 }
 31 
 32 bool dfs( int v )
 33 {
 34     for( int u = 0 ; u<ve[v].size() ; u++ )
 35     {
 36         if( !vis[ ve[v][u] ]  )
 37         {
 38             vis[ ve[v][u] ] = true;
 39             if( linker[ ve[v][u] ]==-1 || dfs( linker[ ve[v][u] ] ) )
 40             {
 41                 linker[ ve[v][u] ] = v;
 42                 return true;
 43             }
 44         }
 45     }
 46     return false;
 47 }
 48 
 49 int maxMatch()
 50 {
 51     int cnt = 0;
 52     memset( linker , -1 , sizeof(linker) );
 53     for( int u = 0 ; u<n ; u++ )
 54     {
 55         memset( vis , false , sizeof(vis) );
 56         if( dfs(u) )
 57             cnt++;
 58     }
 59     return cnt;
 60 }
 61 
 62 int main()
 63 {
 64     int t , i , j;
 65     scanf( "%d",&t );
 66     while( t-- )
 67     {
 68         scanf( "%d",&n );
 69         for( i = 0 ; i<size ; i++ )
 70             ve[i].clear();
 71         //memset( mp , false , sizeof(mp) );
 72         for( i = 0 ; i<n ; i++ )
 73         {
 74             scanf( "%d %c %s %s",&couple[i].height,&couple[i].gendle,couple[i].music,couple[i].sport );
 75         }
 76         /*
 77         for( i = 0 ; i<n ; i++ )
 78         {
 79             for( j = i+1 ; j<n ; j++ )
 80             {
 81                 if( judge(couple[i],couple[j]) )
 82                 {
 83                     ve[i].push_back(j);
 84                 }
 85             }
 86         }
 87          这样就是WA。  我的输出也会变成 n-maxMatch()  */  
 88         for( i = 0 ; i<n ; i++ )
 89         {
 90             for( j = 0 ; j<n ; j++ )
 91             {
 92                 if( judge( couple[i] , couple[j] ) )
 93                     ve[i].push_back(j);
 94             }
 95         }
 96         printf( "%d
", n-maxMatch()/2 );
 97     }
 98     return 0;
 99 }
100

View Code

明天应该都会解决.~~ 去撸一把碎觉 ...

全世界失眠多好

OK 终于AC了并且学到了很多

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int size = 520;
 7 struct data
 8 {
 9     int height;
10     char gendle;
11     char music[110];
12     char sport[110];
13 }couple[size];
14 
15 struct mp  
16 {           
17     int arr[size];  
18     int sum; 
19 }ve[size];
20 
21 bool vis[size];
22 int linker[size];
23 int n;
24 
25 bool judge( const data& p , const data& q )
26 {
27     if( ( (p.height-q.height<-40) || (p.height-q.height>40) ) || p.gendle==q.gendle || strcmp( p.music,q.music)!=0 || !strcmp(p.sport,q.sport) )
28         return false; 
29     return true;   
30 }
31 
32 bool dfs( int v )
33 {
34     for( int u = 0 ; u<ve[v].sum ; u++ )
35     {
36         int temp = ve[v].arr[u];
37         if( !vis[temp]  )
38         {
39             vis[ temp ] = true;
40             if( linker[ temp ]==-1 || dfs( linker[ temp ] ) )
41             {
42                 //linker[v] = temp;
43                 linker[ temp ] = v;
44                 return true;
45             }
46         }
47     }
48     return false;
49 }
50 
51 int maxMatch()
52 {
53     int cnt = 0;
54     memset( linker , -1 , sizeof(linker) );
55     for( int u = 0 ; u<n ; u++ )
56     {
57         //if( linker[u] != -1 ) 
58             //continue; 
59         memset( vis , false , sizeof(vis) );
60         if( dfs(u) )
61             cnt++;
62     }
63     return cnt;
64 }
65 
66 int main()
67 {
68     int t , i , j;
69     scanf( "%d",&t );
70     while( t-- )
71     {
72         scanf( "%d",&n );
73         for( i = 0 ; i<size ; i++ ) 
74         {
75             ve[i].sum = 0;
76         }
77         for( i = 0 ; i<n ; i++ )
78         {
79             scanf( "%d %c %s %s",&couple[i].height,&couple[i].gendle,couple[i].music,couple[i].sport );
80         }
81         for( i = 0 ; i<n ; i++ )
82         {
83             for( j = 0 ; j<n ; j++ )
84             {
85                 if( judge( couple[i] , couple[j] ) )
86                 {
87                     ve[i].arr[ ve[i].sum ] = j; 
88                     ve[i].sum++;
89                 }
90             }
91         } 
92         printf( "%d
", n-maxMatch()/2 );
93         //printf( "%d
", n-maxMatch() ); 
94     }
95     return 0;
96 }

View Code

上述代码注释的方法是大神教我的而且他这种方法更好虽然我们最后都可以AC 但是能追求更好的当然就用更好的不是吗不然优化就没有意义了,,

经过这次发现vector在你的数据规模几百的时候就会很慢了因为你不断的new 会很耗时

这里提供一个可行的解决方案开始的时候使用 reserve()函数你先设置好数组大小

vector 的优点就是动态扩充大小随之付出的就是时间的代价

我用了个邻接表即开个结构体去存储它时间一下子缩短到了300多ms 还是蛮好的

对于这题可能还会有所补充暂时先这样吧~

PS：上边代码中的注释有点错误我这边因为改动不方便就不去修改了 ...要是看不懂再给我留言吧... sorry

just follow your heart