旅行商(TSP)

描述

Shrek是一个大山里的邮递员,每天负责给所在地区的n个村庄派发信件。但杯具的是,由于道路狭窄,年久失修,村庄间的道路都只能单向通过,甚至有些村庄无法从任意一个村庄到达。这样我们只能希望尽可能多的村庄可以收到投递的信件。

Shrek希望知道如何选定一个村庄A作为起点(我们将他空投到该村庄),依次经过尽可能多的村庄,路途中的每个村庄都经过仅一次,最终到达终点村庄B,完成整个送信过程。这个任务交给你来完成。

 

 

输入

第一行包括两个整数n,m,分别表示村庄的个数以及可以通行的道路的数目。

以下共m行,每行用两个整数v1和v2表示一条道路,两个整数分别为道路连接的村庄号,道路的方向为从v1至v2,n个村庄编号为[1, n]。

 

 

输出

输出一个数字,表示符合条件的最长道路经过的村庄数。

 

 

输入样例

4 3

1 4

2 4

4 3

 

 

输出样例

3

 

 

限制

1 ≤ n ≤ 1,000,000

0 ≤ m ≤ 1,000,000

输入保证道路之间没有形成环

时间:2 sec

空间:256MB

 

 

 

 

   呜~~我受够了~~~

   一开始用深度遍历,结果只跑了60分,说我慢了~~然后我就开始憋大招,编了一个晚上,用出度的办法一层层剥掉路径树~~然后想着,先放到OJ上看看对不对再剪枝吧~~~结果,结果清华OJ竟然不让用vector !!!

   简直疯掉了~~从网上找了vector.h打包交上,竟然编译不通过!!!难不成让我自己写几千行的代码?~~一想到我竟然还用到了vector的push_back等函数,就觉得绝望,这要是真写那可就是要写好几个内部的接口函数的啊~~疯掉了~~太晚了~~太打击了~~~我去睡觉了~~

 

   对了,有没有大神来看看我的代码对不对的?

 

 

#include
#include

using namespace std;

vector mgraph;
vector outdegree;
vector length;

int main()
{
   int n,m,v1,v2,i,t;
   cin>>n>>m;
   for(i=0;i    {
       for(t=0;t        {
           mgraph.push_back(0);
       }
       outdegree.push_back(0);
       length.push_back(0);
   }
   //cout<    //cout<<"ok1";
   for(i=0;i    {
       cin>>v1>>v2;
       mgraph[n*v1+v2]=1;
   }
   //cout<<"ok2";

   for(v1=1;v1    {
       t=0;
       for(v2=1;v2        {
           if(mgraph[n*v1+v2]==1) t++;
       }
       outdegree[v1]=t;
   }
   //cout<

   int zero,hight=0;
   vector temp;
   do
   {
       hight++;
       zero=0;
       for(v1=1;v1        {
           if(outdegree[v1]==0 && length[v1]==0)
           {
               zero++;
               length[v1]=hight;//cout<<"v1="<                temp.push_back(v1);//cout<<"temp.capacity()="<            }

 

       }

       for(t=0;t        {
           for(i=1;i            {
               if(mgraph[n*i+temp[t]]==1)
               {
                   mgraph[n*i+temp[t]]=0;outdegree[i]–;
                   //cout<                }
           }
       }
       temp.clear();

       //cout<<"hight="<    }while(zero==1);
   //cout<<"ok5";

   cout<

 

   //cout<    //cout<    return 0;
}

旅行商(TSP)》上有1条评论

  1. Pingback引用通告: BZ编程小组 作品 | BZ编程小组

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.