這題跟前面一題很像吧就是建圖有點麻煩。

注意最后源點和匯點的選擇一定得是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; }

總結

以上是生活随笔為你收集整理的usaco Telecowmunication（网络流）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。