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 |
Re:郁闷,why,哪个大牛可以看一下In Reply To:郁闷,why,哪个大牛可以看一下 Posted by:pkudy at 2004-07-10 04:01:52 我都测了好几组数据了,提交就WA > #include <iostream.h> > #include <stdio.h> > #include <string.h> > #include <ctype.h> > typedef struct > { > int par; > int v; > int p; > }NODE; > void main(void) > { > NODE q[100]; > char str[1000],*p; > int n,i,j,k,m,w,r,u; > bool g[50][50]; > int v[100]; > __int64 s[41][41],t,ans; > memset(s,0,sizeof(s)); > memset(g,0,sizeof(g)); > cin>>n; > cin.getline(str,1000,'\n'); > for(i=1;i<=n;i++) > { > cin.getline(str,1000,'\n'); > p = str; > while(sscanf(p,"%d",&j)!=EOF) > { > g[j][i] = g[i][j] = 1; > s[i][j] |= ((__int64)1<<i)|((__int64)1<<j); > while(p[0]==' ') > p++; > while(isdigit(p[0])) > p++; > } > } > for(i=1;i<=n;i++) > for(j=1;j<=n;j++) > { > if(i==j) > { > s[i][j] |= ((__int64)1<<i); > continue; > } > if(g[i][j]) > continue; > memset(v,0,sizeof(v)); > k = 1; m = 2; > q[1].v = i;q[1].par=0;q[1].p=1;v[i]=1; > while(1) > { > r = q[k].p; > for(w=1;w<=n;w++) > { > if(g[q[k].v][w] && v[w]==0) > { > q[m].v = w; > q[m].par = k; > q[m].p = r + 1; > v[w] = 1; > m++; > } > } > if(v[j]==1) > { > for(w=k;w<m;w++) > { > if(q[w].p>r) > break; > if(g[q[w].v][j] == 1) > { > u = w; > while(u!=0 && q[u].p!=0) > { > q[u].p = 0; > u = q[u].par; > } > } > } > break; > } > k++; > } > s[i][j] |= ((__int64)1<<i)||((__int64)1<<j); > for(w=1;w<m;w++) > { > if(q[w].p == 0) > s[i][j] |= ((__int64)1<<q[w].v); > } > } > for(i=1;i<=n;i++) > for(j=1;j<=n;j++) > { > g[i][j] |= g[j][i]; > g[j][i] |= g[i][j]; > } > t = ((__int64)1<<(n+1)) - 1; > cin>>m; > cin.getline(str,1000,'\n'); > while(m-- >0) > { > cin.getline(str,1000,'\n'); > p = str; k = 0; > while(sscanf(p,"%d",&v[k++])!=EOF) > { > while(p[0]==' ') > p++; > while(isdigit(p[0])) > p++; > } > ans = 0; > for(i=0;i<k;i++) > for(j=0;j<k;j++) > ans |= s[v[i]][v[j]]; > if(ans>=t) > cout<<"yes"<<endl; > else > cout<<"no"<<endl; > } > > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator