> #include <iostream>
> #include <cstdlib>
> #include <memory>
> #include <list>
> using namespace std;
> const int maxn=40001;
> struct node_type
> {
>     int rec,val;
> };
> struct dist_type
> {
>     int pre,val,rec;
> }dist[maxn];
> list<node_type>li[maxn];
> void solve(int root)
> {
>     list<node_type>::iterator i;
>     if(li[root].empty())return;
>     for(i=li[root].begin();i!=li[root].end();i++)
>     {
>         solve(i->rec);
>         if(dist[i->rec].val+i->val>dist[root].val)
>            dist[root].val=dist[i->rec].val+i->val;
>     }
> }
> int main(int argc, char *argv[])
> {
>     int i,j,r,x,y,sum,max,temp_1,temp_2,n,m;char c;
>     list<node_type>::iterator li_i;
>     node_type node;
>     while(cin>>n>>m)
>     {
>           memset(dist,0,sizeof(dist));
>           for(i=1;i<=n;i++)
>               li[i].clear();
>           for(i=1;i<=n;i++)dist[i].rec=i;
>           for(i=0;i<m;i++)
>           {
>               cin>>x>>y>>sum>>c;
>               node.val=sum;
>               if(c=='W' || c=='N')
>               {
>                   dist[x].pre=y;
>                   node.rec=x;
>                   li[y].push_back(node);
>               }
>               else 
>               {
>                    dist[y].pre=x;
>                    node.rec=y;
>                    li[x].push_back(node);
>                }
>            }
>            for(j=1;j<=n;j++)
>                if(!dist[j].pre)
>                {
>                    r=j;
>                    solve(r);
>                 }
>            max=0;
>            for(i=1;i<=n;i++)
>            {
>                   temp_1=temp_2=0;
>                   for(li_i=li[i].begin();li_i!=li[i].end();li_i++)
>                   {
>                       if(li_i->val+dist[li_i->rec].val>temp_1)
>                          temp_1=li_i->val+dist[li_i->rec].val;
>                       else
>                       if(li_i->val+dist[li_i->rec].val>temp_2)
>                          temp_2=li_i->val+dist[li_i->rec].val;
>                   }
>                   if(temp_1+temp_2>max)max=temp_1+temp_2;
>            }
>            for(i=1;i<=n;i++)
>               if(dist[i].val>max)
>                   max=dist[i].val;
>             cout<<max<<endl;
>     }
>     //system("PAUSE");	
>     return 0;
> }

• Re:用BFS代替DFS (8) shit 2004-11-05 23:07:32
  • 无向图，用GCC不会溢出 (0) xiaomi 2004-11-05 23:34:03
    • Keeps WA... 谁有数据？ (3518) shit 2004-11-06 11:45:56
      • 二次BFS可以解决吧 (3746) achilles 2004-11-06 14:57:56