65
技術社區[雲棲]
【Tsinghua】旅行商(TSP)
關於這道題，我要說兩句，這道題我覺得我用拓撲排序的思路肯定是沒錯的，而且也對了幾組數據，但是其他幾組卻超時，肯定是哪裏的代碼優化的不夠好。。。。。。
最後隻得了40分。。。
旅行商(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
提示
拓撲排序
最後提交給那個OJ的代碼：
#include<iostream>
#include <stdio.h>
#include <malloc.h>
#define MAXSIZE 100002
#define TRUE 1
#define FALSE 0
using namespace std;
typedef int VertexData;
typedef int AdjType;
//保存每個節點的最大路數
int Roads[MAXSIZE+1];
int maxRoad=0;
typedef struct Stack //定義棧
{
int data[MAXSIZE+1];
int top;
}Stack;
typedef struct ArcNode //定義弧結點
{
AdjType adj;
ArcNode *nextArc;
}ArcNode;
typedef struct VertexNode //定義頂點
{
VertexData vertexData;
ArcNode *firstArc;
}VertexNode;
typedef struct AdjMatrix //定義圖
{
VertexNode vertexNodes[MAXSIZE+1];
int verNum,arcNum;
}AdjMatrix;
//全局變量
int indegree[MAXSIZE+1]={0};
int LocateGraph(AdjMatrix *g, VertexData vertexData)
{
int iIndex;
for(iIndex=1;iIndex<=g->verNum;iIndex++)
{
if(vertexData==g->vertexNodes[iIndex].vertexData)
return iIndex;
}
return FALSE;
}
void CreateGraph(AdjMatrix *g)
{
int iCount,arcStart,arcEnd;
int start,end;
//輸入有向無環圖的頂點,及弧數
cin>>g->verNum>>g->arcNum;
//輸入有向無環圖的頂點信息
ArcNode *q=NULL;
for(iCount=1;iCount<=g->verNum;iCount++)
{
g->vertexNodes[iCount].vertexData=iCount;
g->vertexNodes[iCount].firstArc=NULL;
}
for(iCount=1;iCount<=g->arcNum;iCount++)
{
//輸入弧的起始與結束的信息
cin>>start>>end;
arcStart=LocateGraph(g,start);
arcEnd=LocateGraph(g,end);
//添加弧結點
q=(ArcNode*)malloc(sizeof(ArcNode));
q->adj=arcEnd;
q->nextArc=g->vertexNodes[arcStart].firstArc;
g->vertexNodes[arcStart].firstArc=q;
//對於第arcEnd個頂點的入度值加1
indegree[arcEnd]++;
}
}
//判棧空
int IsEmpty(Stack *stack)
{
return stack->top==-1?TRUE:FALSE;
}
//初始化棧
void InitStack(Stack *stack)
{
stack->top=-1;
}
//出棧
void Pop(Stack *stack,int *iIndex)
{
*iIndex=stack->data[stack->top--];
}
//進棧
void Push(Stack *stack,int value)
{
stack->data[++stack->top]=value;
}
//拓撲排序
void Tuopu(AdjMatrix *g)
{
int iCount;
Stack *stack=(Stack*)malloc(sizeof(Stack));
InitStack(stack);
ArcNode *p=NULL;
//初始化 路數，都等於1
for(iCount=1;iCount<=g->verNum;iCount++)
Roads[iCount]=1;
//對於入度為0的頂點入棧
for(iCount=1;iCount<=g->verNum;iCount++)
{
if(indegree[iCount]==0){
Push(stack,iCount);
}
}
//輸出拓撲序列
//輸出頂點後，將與該頂點相連的頂點的邊刪除，將與相連頂點的入度減1，如減後為0，入棧，棧空結束
while(!IsEmpty(stack))
{
Pop(stack,&iCount);
//cout<<g->vertexNodes[iCount].vertexData<<" ";
//這裏處理路數
p=g->vertexNodes[iCount].firstArc;
while(p!=NULL)
{
if(--indegree[p->adj]==0)
Push(stack,p->adj);
if(Roads[g->vertexNodes[iCount].vertexData]+1>Roads[p->adj])
Roads[p->adj]=Roads[g->vertexNodes[iCount].vertexData]+1;
if(maxRoad<Roads[p->adj])
maxRoad=Roads[p->adj];
p=p->nextArc;
}
}//end while
//cout<<endl;
}
int main()
{
AdjMatrix *g=(AdjMatrix*)malloc(sizeof(AdjMatrix));
CreateGraph(g);
Tuopu(g);
printf("%d\n",maxRoad);
return 0;
}
結果：
最後更新：2017-04-03 05:39:38