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