NC219624. wzc与小灰
描述
输入描述
第一行为一个整数n和一个整数m，分别代表公园里景点的个数和道路的数量。(1<=n<=50,1<=m<=n*(n+1)/2)接下来m行每行两个整数a和b，代表地点a和b之间存在着一条道路连接。题目保证不存在重复的路径(0<=a,b<=n）第m+2行为一个整数k，代表寻找方案的数量(1<=k<=100)接下来为k行，第2+m+i行代表第i种寻找方案的路径情况。每行的第一个整数L代表该寻找方案的路径长度，之后跟着L个用空格隔开的整数xi，依次代表该寻找方案经过的景点。(1<=L<=100,0<=xi<=n，数据保证至少存在一个有效方案，且不存在当前在景点i，下一个目标仍为景点i的情况)
输出描述
输出一个整数，代表经过不同景点数量最多的有效方案，如果有多个答案，输出长度更长的那个，如果仍然有多个答案，输出编号更小的那个。
示例1
输入:
2 2 0 1 2 1 2 2 2 1 1 1
输出:
2
说明:
示例2
输入:
3 4 0 1 3 0 1 2 3 1 4 2 1 3 3 3 1 2 4 3 0 1 2 4 1 3 1 2
输出:
3
说明:
第2,3,4种方案均经过了3个不同的景点，第3，4种方案的长度均为4，比第2种方案长。而第3，4种方案中第3种方案的编号更小，因此选择方案3。C++(g++ 7.5.0) 解法, 执行用时: 5ms, 内存消耗: 524K, 提交时间: 2022-12-28 22:46:41
#include<bits/stdc++.h>
using namespace std;
int a[505][505],n,m,k;
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
int u,v;cin>>u>>v;
a[u][v]=a[v][u]=1;
}
cin>>k;
int cnt=-1,ans=0,len=0;
for(int j=1;j<=k;j++){
int l,z=0,f=0,vt[505]={0},sum=0;cin>>l;
for(int i=0;i<l;i++){
int x;cin>>x;
if(!a[z][x]){
f=1;
}
z=x;
if(!vt[x]&&x!=0)
sum++,vt[x]=1;
}
if(!f&&(sum>cnt||(sum==cnt&&l>len)))
{
len=l,cnt=sum,ans=j;
}
}
cout<<ans<<endl;
return 0;
}
C++ 解法, 执行用时: 10ms, 内存消耗: 404K, 提交时间: 2022-03-24 21:14:34
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int n,m,a[200][200],t,sign[200];
int main()
{
cin>>n>>m;
while(m--)
{
int u,v;
cin>>u>>v;
a[u][v]=a[v][u]=1;
}
cin>>t;
int ans,fign,sum,l,len,hs;
for(int j=1;j<=t;j++)
{
memset(sign,0,sizeof sign);
int f,x;
cin>>f;
ans=0,fign=1,hs=0;
for(int i=1;i<=f;i++)
{
cin>>x;
if(a[hs][x]&&!sign[x]) sign[x]=1,ans++;
if(!a[hs][x]) fign=0;
hs=x;
}
if(fign&&(ans>sum||(ans==sum&&f>len)))
{
len=f,sum=ans,l=j;
}
}
cout<<l<<endl;
return 0;
}