凋零傲风 @ 2016-11-18 21:33:50
很奇怪!为什么第七个点不过……关键数据还下载不下来,说是太大了,太大了?
// SS[0]中的车站,被认为都是级别1
// SS[1]-SS[0]的车站,被认为都是级别2
// SS[2]-SS[0]-SS[1]的车站,被认为都是级别3
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int Input(vector<vector<int> > &SS);
void InitGraph(vector<vector<int> > &SS, vector<vector<int> >& M);
void Remove(vector<int> &a, vector<int> &b);
int Search(vector<int> &a,int x);
void Print(vector<vector<int> > &SS);
void TopoSort(vector<vector<int> >& G);
int main()
{
// 读文件
vector<vector<int> > SS;
int n=Input(SS);
// 构造有向图的邻接矩阵
vector<vector<int> > G(n,vector<int>(n));
InitGraph(SS, G);
// 分级别拓扑排序
TopoSort(G);
return 0;
}
void TopoSort(vector<vector<int> >& G)
{
int n=G.size();
// 计算入度表
vector<int> inDegree(n,0);
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
if(G[i][j]==1)
inDegree[j]++;
// 入度为0的进队列
queue<pair<int,int> > Q; // <站的下标 站的级别 >
for(int i=0; i<n; i++)
if(inDegree[i]==0)
Q.push( pair<int,int> (i,1) );
pair<int,int> v;
while( !Q.empty() )
{
v=Q.front(); Q.pop();
for(int i=0; i<n; i++)
{
if(G[v.first][i]==1)
{
inDegree[i]--;
if(inDegree[i]==0)
Q.push( pair<int,int> (i,v.second+1) );
}
}
}
cout<<v.second<<endl;
}
void InitGraph(vector<vector<int> > &SS, vector<vector<int> >& G)
{
for(int i=0; i<SS.size(); i++)
{
int s=SS[i][0], e=SS[i][SS[i].size()-1]; // 起点站、终点站
vector<int> nostop;
for(int k=s; k<=e; k++) nostop.push_back(k);
Remove(nostop, SS[i]);
for(int i1=0; i1<nostop.size(); i1++)
for(int j1=0; j1<SS[i].size(); j1++)
{
int ii=nostop[i1], jj=SS[i][j1];
G[ii][jj]=1;
}
}
}
// a-b存入a
void Remove(vector<int> &a, vector<int> &b)
{
for(int i=0; i<b.size(); i++)
{
int k=Search(a,b[i]);
if(k!=-1)
a.erase(a.begin()+k);
}
}
int Search(vector<int> &a,int x)
{
for(int i=0; i<a.size(); i++)
if(a[i]==x)
return i;
return -1;
}
int Input(vector<vector<int> > &SS)
{
int n; cin>>n; // 车站数
int m; cin>>m; // 车次数
for(int i=0; i<m; i++)
{
int k; cin>>k; // 每次车的停站数
vector<int> Si; // 每次车的停站向量
for(int j=0; j<k; j++)
{
int id; cin>>id; id--;
Si.push_back(id);
}
SS.push_back(Si);
}
return n;
}
by KEIONG @ 2017-08-17 09:24:09
我第七和第八TLE orz