这题跟前面一题很像吧就是建图有点麻烦。
注意最后源点和汇点的选择一定得是2*a和2*b-1不然就是错的。
/* ID:jinbo wu TASK:telecow LANG:C++ */ #include<bits/stdc++.h> using namespace std; #define inf 100000000 struct node { int c,f; }g[220][220]; int ans[220]; int n,m,a,b; int level[220]; int cnt; void init() { for(int i=1;i<=2*n;i++) { for(int j=1;j<=2*n;j++) g[i][j].f=0; } } bool bfs() { queue<int> q; memset(level,0,sizeof(level)); q.push(2*a); level[2*a]=1; int u,v; while(!q.empty()) { u=q.front(); q.pop(); for(int v=1;v<=2*n;v++) { if(!level[v]&&g[u][v].c>g[u][v].f) { level[v]=level[u]+1; q.push(v); } } } return level[2*b-1]!=0; } int dfs(int u,int cp) { int tmp=cp; int v,t; if(u==2*b-1) return cp; for(v=1;v<=2*n&&tmp;v++) { if(level[u]+1==level[v]) { if(g[u][v].c>g[u][v].f) { t=dfs(v,min(tmp,g[u][v].c-g[u][v].f)); g[u][v].f+=t; g[v][u].f-=t; tmp-=t; } } } return cp-tmp; } int dinic() { int sum,tf; sum=tf=0; while(bfs()) { while(tf=dfs(a*2,inf)) { sum=sum+tf; } } return sum; } int main() { freopen("telecow.in","r",stdin); freopen("telecow.out","w",stdout); int x,y; cin>>n>>m>>a>>b; for(int i=1;i<=m;i++) { cin>>x>>y; g[x*2-1][x*2].c=1; g[y*2-1][y*2].c=1; g[x*2][y*2-1].c=inf; g[y*2][x*2-1].c=inf; } int s=dinic(); int f=s; int l=0; for(int i=1;i<=n;i++) { if(i==a||i==b) continue; init(); g[i*2-1][i*2].c=0; if(dinic()+1==s) { ans[l++]=i; cnt++; s--; if(cnt==f) break; } else g[i*2-1][i*2].c=1; } cout<<l<<endl; for(int i=0;i<l-1;i++) { cout<<ans[i]<<" "; } cout<<ans[l-1]<<endl; }