Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

二次BFS可以解决吧

Posted by achilles at 2004-11-06 14:57:56 on Problem 1985
In Reply To:Keeps WA... 谁有数据? Posted by:shit at 2004-11-06 11:45:56
> #include <iostream>
> #include <cstdlib>
> #include <memory>
> using namespace std;
> const int maxn=40001;
> struct dist_type
> {
>     int pre,val;
> }dist[maxn];
> int q[maxn],al[maxn][4],len[maxn][4],ans[maxn][2];
> bool e[maxn];
> void build_tree(int root)
> {
>            int head,tail,temp,i,j;
>            head=tail=0;q[0]=root;
>            e[root]=1;
>            do
>            {
>                 temp=tail;
>                 for(i=head;i<=temp;i++)
>                 {
>                     for(j=0;j<4;j++)
>                         if(!al[q[i]][j])break;
>                         else
>                         if(!e[al[q[i]][j]])
>                         {
>                            dist[al[q[i]][j]].pre=q[i];
>                            tail++;
>                            q[tail]=al[q[i]][j];
>                            e[al[q[i]][j]]=1;
>                         }
>                 }
>                 head=temp+1;        
>            }while(tail>=head);
> }
> int main(int argc, char *argv[])
> {
>     int i,j,x,y,head,tail,temp,sum,max,n,m;
>     char c;
>     while(cin>>n>>m)
>     {
>           memset(dist,0,sizeof(dist));
>           memset(e,0,sizeof(e));
>           memset(ans,0,sizeof(ans));
>           memset(al,0,sizeof(al));
>           for(i=0;i<m;i++)
>           {
>               fin>>x>>y>>sum>>c;
>               for(j=0;j<4;j++)
>                   if(!al[x][j])
>                   {
>                      al[x][j]=y;
>                      len[x][j]=sum;
>                      break;
>                   }
>               for(j=0;j<4;j++)
>                   if(!al[y][j])
>                   {
>                      al[y][j]=x;
>                      len[y][j]=sum;
>                      break;
>                   }
>            }
>            for(i=1;i<=n;i++)
>                if(!dist[i].pre)
>                   build_tree(i);
>            head=0;tail=-1;
>            for(i=1;i<=n;i++)
>                if(dist[i].pre)
>                   e[dist[i].pre]=0;
>            for(i=1;i<=n;i++)
>            {
>                if(e[i])
>                {
>                   tail++;q[tail]=i;
>                }
>            }
>            do
>            {
>                 temp=tail;
>                 for(i=head;i<=temp;i++)
>                 {
>                     if(!dist[q[i]].pre)continue;
>                     if(!e[dist[q[i]].pre])
>                     {
>                        tail++;q[tail]=dist[q[i]].pre;
>                        e[q[tail]]=1;
>                     }
>                     for(j=0;j<4;j++)
>                         if(al[q[i]][j]==dist[q[i]].pre)
>                            break;
>                     if(len[q[i]][j]+dist[q[i]].val>dist[dist[q[i]].pre].val)
>                        dist[dist[q[i]].pre].val=len[q[i]][j]+dist[q[i]].val;
>                     if(len[q[i]][j]+dist[q[i]].val>ans[dist[q[i]].pre][0])
>                     {
>                        ans[dist[q[i]].pre][1]=ans[dist[q[i]].pre][0];                 
>                        ans[dist[q[i]].pre][0]=len[q[i]][j]+dist[q[i]].val;
>                     }
>                     else
>                     if(len[q[i]][j]+dist[q[i]].val>ans[dist[q[i]].pre][1])
>                        ans[dist[q[i]].pre][1]=len[q[i]][j]+dist[q[i]].val;
>                 }
>                 head=temp+1;        
>            }while(tail>=head);
>            max=0;
>            for(i=1;i<=n;i++)
>                if(ans[i][0]+ans[i][1]>max)
>                   max=ans[i][0]+ans[i][1];
>            cout<<max<<endl;
>     }
>     //system("PAUSE");	
>     return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator