全部评论
一个团体可以🈶️多个接口人……感觉会有公共路径
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
using namespace std;
typedef struct TeamType
{
vector<int> meetMan;
};
void DFSTrave(int team1,int team2,TeamType *TeamMan,bool *visite,vector<int>&legalRoad,vector<vector<int>>&allLegalRoad)
{
visite[team1] = true;
for(int i = 0;i < TeamMan[team1].meetMan.size();i++)
{
if(TeamMan[team1].meetMan[i] == team2)
{
allLegalRoad.push_back(legalRoad);
}
else if(visite[TeamMan[team1].meetMan[i]] == false)
{
legalRoad.push_back(TeamMan[team1].meetMan[i]);
DFSTrave(TeamMan[team1].meetMan[i],team2,TeamMan,visite,legalRoad,allLegalRoad);
legalRoad.erase(legalRoad.end()-1);
visite[TeamMan[team1].meetMan[i]] = false;
}
}
}
void FindRoad(int team1,int team2,int N,TeamType *TeamMan,bool *visite,vector<int>&legalRoad,vector<vector<int>>&allLegalRoad)
{
for(int i = 1;i <= N;i++)
visite[i] = false;
DFSTrave(team1,team2,TeamMan,visite,legalRoad,allLegalRoad);
}
int JudeSameNodeOfRoad(vector<vector<int>>&allLegalRoad)
{
int count = 0;
map<int,int> nodeCount;
for(int i = 0;i < allLegalRoad.size();i++)
{
for(int j = 0;j < allLegalRoad[i].size();j++)
{
nodeCount[allLegalRoad[i][j]]++;
}
}
int maxValue = 0;
map<int,int>::iterator it;
for(it = nodeCount.begin();it != nodeCount.end();it++)
{
if(maxValue < it->second)
maxValue = it->second;
}
return allLegalRoad.size()-maxValue+1;
}
int main()
{
int N,M,team1,team2;
cin>>N>>M>>team1>>team2;
TeamType *TeamMan = new TeamType[N+1];
bool *visite = new bool[N+1];
vector<int> legalRoad;
vector<vector<int>> allLegalRoad;
for(int i = 0;i < M;i++)
{
int tempTeam1,tempTeam2;
cin>> tempTeam1>>tempTeam2;
TeamMan[tempTeam1].meetMan.push_back(tempTeam2);
TeamMan[tempTeam2].meetMan.push_back(tempTeam1);
}
FindRoad(team1,team2,N,TeamMan,visite,legalRoad,allLegalRoad);
int minNode = JudeSameNodeOfRoad(allLegalRoad);
cout<<minNode<<endl;
return 0;
}
为什么这个代码一直内存超限?有大神知道吗?我看题目内存要求大概有65M呢?
相关推荐
点赞 评论 收藏
分享
02-05 21:13
上海交通大学 平台产品 点赞 评论 收藏
分享