首页 > 代码库 > hiho 第116周,最大流最小割定理,求最小割集S,T
hiho 第116周,最大流最小割定理,求最小割集S,T
#include <bits/stdc++.h>using namespace std;#define maxn 505#define INF 0x3f3f3f3fstruct Edge{ int from,to,cap,flow;};struct Dinic{ int n,m,s,t; vector<Edge> edge; vector<int> G[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; void addEdge (int from,int to,int cap) { edge.push_back((Edge){from,to,cap,0}); edge.push_back((Edge){to,from,0,0}); m = edge.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BFS() { memset(vis,0,sizeof(vis)); queue<int> Q; Q.push(s); d[s] = 0; vis[s] = 1; while(!Q.empty()) { int x = Q.front(); Q.pop(); for(int i=0; i<G[x].size(); i++) { Edge & e = edge[G[x][i]]; if(!vis[e.to]&&e.cap>e.flow) { vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } int DFS(int x,int a) { if(x==t||a==0) return a; int flow = 0,f; for(int & i = cur[x]; i<G[x].size(); i++) { Edge & e = edge[G[x][i]]; if(d[x] + 1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0) { e.flow +=f; edge[G[x][i]^1].flow -=f; flow +=f; a-=f; if(a==0) break; } } return flow; } int Maxflow (int s,int t) { this->s = s;this->t = t; int flow = 0; while(BFS()) { memset(cur,0,sizeof(cur)); flow+=DFS(s,INF); } return flow; } //求最小割S,T; void new_BFS(int s,int n) { memset(vis,0,sizeof(vis)); d[s] = 0; vis[s] = 1; queue<int> Q; Q.push(s); while(!Q.empty()) { int u = Q.front(); Q.pop(); for(int i=0;i<G[u].size();i++) { Edge & e = edge[G[u][i]]; if(!vis[e.to]&&e.cap>e.flow) { vis[e.to] = 1; d[e.to] = d[u] + 1; Q.push(e.to); } } } int cnt = 0; for(int i=1;i<=n;i++) { if(vis[i]) cnt++; } printf("%d\n",cnt); for(int i=1;i<=n;i++) if(vis[i]) printf("%d ",i); puts(""); }}sol;int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { int u,v,cap; scanf("%d%d%d",&u,&v,&cap); sol.addEdge(u,v,cap); } printf("%d ",sol.Maxflow(1,n)); sol.new_BFS(1,n); return 0;}
hiho 第116周,最大流最小割定理,求最小割集S,T
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。