| ||||||||||
| 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 | |||||||||
原来memset有增大内存的效果:一开始内存为1060k,用了memset后瞬间变为24000+k
神奇呀
#include <cstdio>
#include <cstring>
#define min(a,b)(a<b?a:b)
#define N 10010
#define M 20010
int n, m, dfn[N]= {0}, low[N], h[N], e[M], ne[M], idx, t, num, time ;
bool map[20000][20000] = {0};
void add (int a, int b)
{
e[idx] = b; ne[idx] = h[a]; h[a] = idx ++ ;
}
int tarjan (int u, int v)
{
int i, s = 0 ;
dfn[u] = low[u] = ++ time ;
for (i = h[u]; i != -1; i = ne[i])
if (!dfn[e[i]]){
t = tarjan (e[i], u) ;
low[u] = min(low[u], low[e[i]]) ;
if (low[e[i]] > dfn[u]) num += !t, s ++ ;
else s += t ;}
else if (e[i] != v && dfn[e[i]] < dfn[u]) low[u] = min(low[u], dfn[e[i]]) ;
return s ;
}
int main ()
{
int i, j ;
scanf ("%d%d", &n, &m) ;
idx = num = time = 0 ;
memset (h, -1, sizeof h) ;
memset (map, 0, sizeof map) ;
while (m -- ){
scanf ("%d%d", &i, &j) ;
if (!map[i][j]){
add (i, j) ;
add (j, i) ;
map[i][j] = map[j][i] = 1 ;}}
num += tarjan (1, -1) == 1 ;
printf ("%d\n", (num + 1) >> 1) ;
return 0 ;
}
大家快看呀, 我开了一个381MB的数组,居然status里却写着1000+k
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator