题意是选出两条从左往右的中间点不能重复选的路径,并使得经过的所有点数最大
可以考虑最大费用最大流,即把所有点拆点,入点向出点中间连容量为1,费用为1的边,然后按照题目中的关系把左边点的出点和右边点的入点连容量为1,费用为0的边(起点和终点的中间边容量为2);源点到起点,终点到汇点连容量为2,费用为0的边
输出方案就反向从汇点找增广路,记录路径即可
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define inf 1061109567
using namespace std;
const int N=200+10,M=5000+10;
il LL rd()
{
re LL x=0,w=1;re char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int to[M<<1],nt[M<<1],hd[N],tot=1;
int c[M<<1],w[M<<1];
il void add(int x,int y,int z,int zz)
{
++tot,to[tot]=y,nt[tot]=hd[x],c[tot]=z,w[tot]=zz ,hd[x]=tot;
++tot,to[tot]=x,nt[tot]=hd[y],c[tot]=0,w[tot]=-zz,hd[y]=tot;
}
int n,m,ss,tt,ans,ff;
int pr[N],di[N],fl[N];
bool v[N];
il bool fyl()
{
memset(di,-63,sizeof(di));
memset(pr,0,sizeof(pr));
memset(fl,0,sizeof(fl));
di[ss]=0;
queue<int> q;
q.push(ss),v[ss]=true,fl[ss]=inf;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(c[i]>0&&di[y]<di[x]+w[i])
{
di[y]=di[x]+w[i];
pr[y]=i,fl[y]=min(fl[x],c[i]);
if(!v[y]) q.push(y);
v[y]=true;
}
}
v[x]=false;
}
if(di[tt]<=di[tt+1]) return false;
ff+=fl[tt],ans+=di[tt]*fl[tt];
int nw=tt;
while(nw!=ss)
{
int j=pr[nw];
c[j]-=fl[tt],c[j^1]+=fl[tt];
nw=to[j^1];
}
return true;
}
char cc[N][16];
map<string,int> mp;
vector<int> an;
int main()
{
bool spc=false;
n=rd(),m=rd();
ss=1,tt=(n+2)<<1;
for(int i=1;i<=n;i++)
{
scanf("%s",cc[i]);
mp[cc[i]]=i;
}
for(int i=1;i<=m;i++)
{
char ss[16],zz[16];
scanf("%s%s",ss,zz);
int x=mp[ss],y=mp[zz];
if(x>y) swap(x,y);
spc|=(x==1&&y==n);
add(x<<1|1,y<<1,1,0);
}
for(int i=2;i<n;i++) add(i<<1,i<<1|1,1,1);
add(ss,1<<1,2,0),add(1<<1,1<<1|1,2,1),add(n<<1,n<<1|1,2,1),add(n<<1|1,tt,2,0);
while(fyl());
if(ff==1&&spc) {printf("2
%s
%s
%s
",cc[1],cc[n],cc[1]);return 0;} //特判只有一条起点到终点的边的情况
if(ff<2) {puts("No Solution!");return 0;}
printf("%d
",ans-2);
int x=tt;
while(x!=ss)
{
for(int i=hd[x];i;i=nt[i])
{
if(c[i]<=0||to[i]>x) continue;
x=to[i],pr[to[i]]=i;
break;
}
if((x&1)&&x>1) an.push_back(x>>1);
}
while(x!=tt)
{
int j=pr[x];
--c[j],++c[j^1];
x=to[j^1];
}
int len=an.size();
for(int i=0;i<len/2;i++) swap(an[i],an[len-i-1]);
--len;
an.erase(an.begin()+len);
while(x!=ss)
{
for(int i=hd[x];i;i=nt[i])
{
if(c[i]<=0||to[i]>x) continue;
x=to[i],pr[to[i]]=i;
break;
}
if((x&1)&&x>1) an.push_back(x>>1);
}
/*while(x!=tt)
{
int j=pr[x];
--w[j],++w[j^1];
x=to[j^1];
}*///这部分在题目中没用,就注释掉了
len=an.size();
for(int i=0;i<len;i++) printf("%s
",cc[an[i]]);
return 0;
}