完了这题好厉害……字符串什么的好麻烦……
要求从$1$到$n$的路径，不重复，经过边数最多
每一个点拆成两个，$A_i,B_i$，然后$A_i$到$B_i$连容量为$1$，费用为$1$的边，保证每个点只被选一次
然后$1$和$n$的话要容量为$2$
然后有连边的话，$B_i$向$A_j$连边，容量$1$，费用$1$
要选的点最多，那么就是要费用最大，所以跑一个最大费用流
然后找方案的话，直接dfs，然后正着和倒着输出
有几个细节，写在代码里了
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<queue> 6 #include<map> 7 #define inf 0x3f3f3f3f 8 using namespace std; 9 const int N=5005,M=500005; 10 int ver[M],Next[M],head[N],edge[M],flow[M],tot=1; 11 int dis[N],disf[N],Pre[N],last[N],vis[N],maxflow,maxcost; 12 int n,m,s,t;bool check=0; 13 queue<int> q; 14 map<string,int> mp; 15 string name[N]; 16 inline void add(int u,int v,int f,int e){ 17 ver[++tot]=v,Next[tot]=head[u],head[u]=tot,flow[tot]=f,edge[tot]=e; 18 ver[++tot]=u,Next[tot]=head[v],head[v]=tot,flow[tot]=0,edge[tot]=-e; 19 } 20 bool spfa(){ 21 memset(dis,0xef,sizeof(dis)); 22 q.push(s),dis[s]=0,disf[s]=inf,Pre[t]=-1; 23 while(!q.empty()){ 24 int u=q.front();q.pop();vis[u]=0; 25 for(int i=head[u];i;i=Next[i]){ 26 int v=ver[i]; 27 if(flow[i]&&dis[v]<dis[u]+edge[i]){ 28 dis[v]=dis[u]+edge[i],last[v]=i,Pre[v]=u; 29 disf[v]=min(disf[u],flow[i]); 30 if(!vis[v]) vis[v]=1,q.push(v); 31 } 32 } 33 } 34 return ~Pre[t]; 35 } 36 void dinic(){ 37 while(spfa()){ 38 int u=t;maxflow+=disf[t],maxcost+=disf[t]*dis[t]; 39 while(u!=s){ 40 flow[last[u]]-=disf[t]; 41 flow[last[u]^1]+=disf[t]; 42 u=Pre[u]; 43 } 44 } 45 } 46 int ans[1005];int num=0; 47 void out(int u){ 48 ans[++num]=u; 49 for(int i=head[u];i;i=Next[i]){ 50 if(flow[i]==0&&edge[i]>=0){ 51 out(ver[i]); 52 flow[i]=1; 53 return; 54 } 55 } 56 } 57 int main(){ 58 //freopen("testdata.in","r",stdin); 59 string s1,s2; 60 scanf("%d%d",&n,&m); 61 for(int i=1;i<=n;++i){ 62 cin>>s1; 63 mp[s1]=i; 64 name[i]=s1; 65 add(i,i+n,1,1); 66 } 67 for(int i=1;i<=m;++i){ 68 cin>>s1>>s2; 69 int a=mp[s1],b=mp[s2]; 70 if(a>b) swap(a,b); 71 if(a==1&&b==n) check=1; 72 add(a+n,b,1,1); 73 } 74 add(1,n+1,1,1),add(n,n+n,1,1); 75 s=1,t=n+n; 76 dinic(); 77 if(!maxflow||(maxflow==1&&!check)) return puts("No Solution!"),0; 78 if(maxflow==1&&check){cout<<2<<' '<<name[1]<<' '<<name[n]<<' '<<name[1]<<' ';return 0;} 79 printf("%d ",maxcost/2-1); 80 //这里的最多城市数是这个 81 //因为考虑如果边连成一个环，边数等于点数 82 //然后每个点拆成两个，除以二 83 //然后因为s'和t'被重复了两次，减去1 84 out(s); 85 for(int i=1;i<=num;++i) if(ans[i]<=n) cout<<name[ans[i]]<<' '; 86 num=0; 87 out(s); 88 for(int i=num-2;i;--i) if(ans[i]<=n) cout<<name[ans[i]]<<' '; 89 //最后两个肯定是t和t'，不用管 90 return 0; 91 }