| ||||||||||
| 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:睡觉去啦In Reply To:郁闷,why,哪个大牛可以看一下 Posted by:pkudy at 2004-07-10 04:01:52 > #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++)
> {
> s[i][j] |= s[j][i];////////////还是不行
> s[j][i] |= s[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