比赛时用dp想了两个小时。。
看了题解说是网络流，感觉被打脸。
知道了这个模型之后，这题就是套个模板直接水过的了。
先拆点限流，把mid当源点，然后把a做汇点跑一次网络流，再把b做汇点跑一次网络流。 mdwzszz
(第一次网络流，分两次跑)
code：
// // main.cpp // jisuanke11215 // // Created by New_Life on 16/7/4. // Copyright © 2016年 chenhuan001. All rights reserved. // //网络流，教育了我 #include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; //网络流SAP模板，复杂度O（N^2*M） //使用前调用init（源点，汇点，图中点的个数），然后调用add_edge()加边 //调用getflow得出最大流 #define N 220 #define M N*N #define INF 0x3fffff struct Max_Flow { struct node { int to,w,next; }edge[M]; int s,t; int nn; int cnt,pre[N]; int lv[N],gap[N]; void init(int ss,int tt,int num) { // s=ss; // t=tt; nn = num;// cnt=0; memset(pre,-1,sizeof(pre)); } void add_edge(int u,int v,int w)//同时建两条边 { edge[cnt].to=v; edge[cnt].w=w; edge[cnt].next=pre[u]; pre[u]=cnt++; edge[cnt].to=u; edge[cnt].w=0; edge[cnt].next=pre[v]; pre[v]=cnt++; } int sdfs(int k,int w) { if(k==t) return w; int f=0; int mi=nn-1; for(int p=pre[k];p!=-1;p=edge[p].next) { int v=edge[p].to,tw=edge[p].w; if(tw!=0) { if(lv[k]==lv[v]+1) { int tmp=sdfs(v,min(tw,w-f)); f+=tmp; edge[p].w-=tmp; edge[p^1].w+=tmp; if(f==w||lv[s]==nn) break; } if(lv[v]<mi) mi=lv[v]; } } if(f==0) { gap[lv[k]]--; if( gap[ lv[k] ]==0 ) { lv[s]=nn; } lv[k]=mi+1; gap[lv[k]]++; } return f; } int getflow() { int sum=0; memset(lv,0,sizeof(lv)); memset(gap,0,sizeof(gap)); gap[0]=nn; while(lv[s]<nn) { sum+=sdfs(s,INF); } return sum; } }mxf; int mat[110][110]; int main(int argc, const char * argv[]) { int T; cin>>T; while(T--) { int n,m; cin>>n>>m; int a,b,mid; cin>>a>>b>>mid; memset(mat,0,sizeof(mat)); for(int i=0;i<m;i++) { int u,v; cin>>u>>v; mat[u][v] = mat[v][u] = 1; } //然后就就构建网络流 mxf.init(0, 0, 2*n+2); for(int i=1;i<=n;i++) { if(i!=mid) mxf.add_edge(2*i, 2*i+1, 1); for(int j=i+1;j<=n;j++) { if(mat[i][j] == 0) continue; if(j!=mid) mxf.add_edge(2*i+1, 2*j, 10); if(i!=mid) mxf.add_edge(2*j+1, 2*i, 10); } } mxf.s = 2*mid+1; mxf.t = 2*a+1; mxf.getflow(); mxf.t = 2*b+1; mxf.getflow(); //找到两次流之后，就是求路径了 int ans[110]; int anscnt=0; int pp = a; while(pp!=mid) { printf("%d ",pp); for(int p=mxf.pre[2*pp];p!=-1;p=mxf.edge[p].next) { int v = mxf.edge[p].to; if(mxf.edge[p].w == 0) continue; pp = v/2; break; } } printf("%d",mid); pp = b; while(pp!=mid) { ans[anscnt++] = pp; for(int p=mxf.pre[2*pp];p!=-1;p=mxf.edge[p].next) { int v = mxf.edge[p].to; if(mxf.edge[p].w == 0) continue; pp = v/2; break; } } for(int i=anscnt-1;i>=0;i--) printf(" %d",ans[i]); printf(" "); } return 0; } /** 1 5 5 2 4 3 1 2 2 3 3 4 4 5 5 1 */