思路：
根据最大流最小割定理可得最大流与最小割相等，所以可以先跑一遍EdmondsKarp算法。
接下来要求的是经过最小割切割后的图中$S$所属的点集。
本来的思路是用并查集处理所有前向边构成的残量网络，如果当前边的残量不为零，则合并两个端点。
然而这样子会WA，因为这只适用于无向图的情况，而流网络属于有向图。
解决的方法是用一个DFS，处理出所有从$S$出发可到达的点，如果边的残量为零则说明当前边不可用。
1 #include<set> 2 #include<queue> 3 #include<cstdio> 4 #include<cctype> 5 #include<vector> 6 #include<cstring> 7 inline int getint() { 8 char ch; 9 while(!isdigit(ch=getchar())); 10 int x=ch^'0'; 11 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 12 return x; 13 } 14 const int N=501,M=20000,inf=0x7fffffff; 15 struct Edge { 16 int from,to,remain; 17 }; 18 Edge e[M<<1]; 19 std::vector<int> g[N]; 20 int sz=0; 21 inline void add_edge(const int u,const int v,const int w) { 22 e[sz]=(Edge){u,v,w}; 23 g[u].push_back(sz); 24 sz++; 25 } 26 int n,m,s,t; 27 int a[N],p[N]; 28 inline int Augment() { 29 memset(a,0,sizeof a); 30 a[s]=inf; 31 std::queue<int> q; 32 q.push(s); 33 while(!q.empty()&&!a[t]) { 34 int x=q.front(); 35 q.pop(); 36 for(unsigned i=0;i<g[x].size();i++) { 37 Edge &y=e[g[x][i]]; 38 if(!a[y.to]&&y.remain) { 39 p[y.to]=g[x][i]; 40 a[y.to]=std::min(a[x],y.remain); 41 q.push(y.to); 42 } 43 } 44 } 45 return a[t]; 46 } 47 inline int EdmondsKarp() { 48 int maxflow=0; 49 while(int flow=Augment()) { 50 for(int i=t;i!=s;i=e[p[i]].from) { 51 e[p[i]].remain-=flow; 52 e[p[i]^1].remain+=flow; 53 } 54 maxflow+=flow; 55 } 56 return maxflow; 57 } 58 bool v[N]={0}; 59 std::vector<int> ans; 60 inline void FindSet(const int x) { 61 v[x]=true; 62 ans.push_back(x); 63 for(unsigned int i=0;i<g[x].size();i++) { 64 if((g[x][i]&1)||v[e[g[x][i]].to]||!e[g[x][i]].remain) continue; 65 FindSet(e[g[x][i]].to); 66 } 67 } 68 int main() { 69 n=getint(),m=getint(); 70 s=1,t=n; 71 while(m--) { 72 int u=getint(),v=getint(),w=getint(); 73 add_edge(u,v,w); 74 add_edge(v,u,0); 75 } 76 printf("%d ",EdmondsKarp()); 77 FindSet(s); 78 printf("%u ",ans.size()); 79 for(unsigned int i=0;i<ans.size()-1;i++) { 80 printf("%d ",ans[i]); 81 } 82 printf("%d ",ans.back()); 83 return 0; 84 }