性质
流量平衡：对于非s，t的点，出入的流量之和为0。
对于如何求一组最小割边
从S开始dfs，标记为true，对于一条边，如果一端为true，另一端为false，那么这条边就属于割边。
关键割边：对于该边如果该边容量增加，那么网络的总流量增加。
：在最大流后的残余网络中，从S开始dfs标记点属于S集合，从T反向dfs标记属于T集合，如果一个边一端属于S集合，一端属于T集合，那么该边就是关键边。
（满流边不一定是关键边
如果对于所有点，要么属于S集合，要么属于T集合，那么对于这个图中，割是唯一的。
总结一下. 下面简称bfs为，把残余网络上bfs,即G[p]>0才算有边，情况下的bfs. (1)求最小割方案（任意）【原来写过一篇日志】 由S开始bfs，bfs到的点为一个割集。剩下的点为一个T的割集。 (2)点属于的割集 必在S割集的点: 所有由S开始bfs到达的点 必在T割集的点: 所有由T开始bfs到达的点 剩下的点: 可不确定. [为啥？MARK下] (3)判断最小割的唯一性 【BZOJ 秘密任务】 如果所有点都可由S或T开始bfs到，则唯一。否则，不唯一。 (4)是否割边【AHOI 2009 最小割】
首先求一个最大流。
有可能在某个最小割中的边(u,v)：满流，删掉之后在残余网络中找不到u到v的路径。
一定在所有最小割中的边(u,v)：满流，s出发沿残余网络能到u，v出发沿残余网络能到t。
实现方法：在残余网络中tarjan求强连通分量。(u,v)两点在同一SCC中说明残余网络中存在u到v路径。s和u在同一scc说明s能到u，t和v同一scc说明v能到t。
bzoj1797（求关键割边和可能割边）
#include<cstdio> #include<stack> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #define N 4005 #define M 60005 using namespace std; const int inf=0x3f3f3f3f; int n,m,S,T; int tot,head[N]; struct aa { int to,pre,cap,flow,from; }edge[M*2]; void addedge(int u,int v,int c) { edge[++tot].to=v;edge[tot].from=u;edge[tot].pre=head[u];head[u]=tot;edge[tot].cap=c; edge[++tot].to=u;edge[tot].from=v;edge[tot].pre=head[v];head[v]=tot;edge[tot].cap=0; } int lev[N]; bool bfs() { memset(lev,0,sizeof(lev)); lev[S]=1; queue<int> q; q.push(S); while (!q.empty()) { int u=q.front();q.pop(); for (int i=head[u];i;i=edge[i].pre) if (lev[edge[i].to]==0&&edge[i].cap>edge[i].flow) { lev[edge[i].to]=lev[u]+1; q.push(edge[i].to); if (edge[i].to==T) return true; } } return false; } int cur[N]; int dfs(int u,int maxflow) { if (u==T||maxflow==0) return maxflow; int ans=0; for (int &i=cur[u];i;i=edge[i].pre) if (lev[edge[i].to]==lev[u]+1) { int flow=dfs(edge[i].to,min(maxflow,edge[i].cap-edge[i].flow)); ans+=flow; maxflow-=flow; edge[i].flow+=flow; edge[((i-1)^1)+1].flow-=flow; if (maxflow==0) return ans; } return ans; } void work() { int ans=0; while (bfs()) { for (int i=1;i<=n;i++) cur[i]=head[i]; ans+=dfs(S,inf); } } int dfn[N],low[N],pos[N],id,ans; stack<int> s; bool in[N]; void Dfs(int u) { dfn[u]=low[u]=++id;in[u]=true;s.push(u); for (int i=head[u];i;i=edge[i].pre) if (edge[i].cap>edge[i].flow) { int v=edge[i].to; if (!dfn[v]) { Dfs(v); low[u]=min(low[u],low[v]); }else if (in[v]) low[u]=min(low[u],dfn[v]); } if (low[u]==dfn[u]) { int v; ans++; do { v=s.top();s.pop(); pos[v]=ans;//缩点只是求个pos而已，不麻烦 in[v]=false; }while (v!=u); } } int main() { scanf("%d%d%d%d",&n,&m,&S,&T); int x,y,c; for (int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&c); addedge(x,y,c); } work(); for (int i=1;i<=n;i++) if (!dfn[i]) Dfs(i); for (int i=1;i<=tot;i+=2) { int u=edge[i].from,v=edge[i].to; if (edge[i].flow<edge[i].cap) {printf("0 0\n");continue;}//注意要保证改变满流 if (pos[u]!=pos[v]) printf("1 ");else printf("0 "); if (pos[u]==pos[S]&&pos[v]==pos[T]) printf("1\n");else printf("0\n"); } return 0; }
总结
1：一般缩点题目的步骤
读入图——缩点，求出pos数组——重新建图——用新图来处理题目
最小割计数
：暂无多项式算法，但平面图最小割数量可转为平面图最短路计数
最小割树
是一颗代表了所有源目节点对间的最小割的树。求解出，就可以了解两两节点对之间的最大流（最大流最小割定理）。（两点间树上路径最小值即为两点最小割）
针对的是无向图。
其实不要被最小割树这个名词吓到。。
首先要知道，任意两点之间的最小割，不同的只有n-1个。（知道就好啦，证明什么的不会QAQ
那么构建最小割树的流程是这样的：
1.集合中随便找两个点，求这两点的最小割
2.用求出的最小割更新s，t两个集合之间点的最小割（或者可以直接建边（S->T），那么最终两点之间的最小割就是两点之间路径的最小权值
3.对s,t两个集合递归处理
其实是非常easy的一个东西，知道性质就行了。
题目:ZJOI2011最小割 ，CQOI2016最小割
:
/************************************************************** Problem: 4519 User: zhhx Language: C++ Result: Accepted Time:5792 ms Memory:8104 kb ****************************************************************/ #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=1005; const int M=105050; const int inf=0x3f3f3f3f; int n,m; int head[N],tot; struct aa { int to,pre,cap,flow; }edge[M*2]; void addedge(int u,int v,int c) { edge[++tot].to=v;edge[tot].pre=head[u];edge[tot].cap=c;head[u]=tot; edge[++tot].to=u;edge[tot].pre=head[v];edge[tot].cap=0;head[v]=tot; } int lev[N],cur[N],S,T; bool bfs() { memset(lev,0,sizeof(lev)); queue<int> q;q.push(S);lev[S]=1; while (!q.empty()) { int u=q.front();q.pop(); for (int i=head[u];i;i=edge[i].pre) if (edge[i].cap>edge[i].flow&&lev[edge[i].to]==0) { lev[edge[i].to]=lev[u]+1; if (edge[i].to==T) return true; q.push(edge[i].to); } } return false; } int dfs(int u,int maxflow) { if (u==T||maxflow==0) return maxflow; int ans=0; for (int &i=cur[u];i;i=edge[i].pre) if (lev[edge[i].to]==lev[u]+1) { int flow=dfs(edge[i].to,min(maxflow,edge[i].cap-edge[i].flow)); ans+=flow; maxflow-=flow; edge[i].flow+=flow; edge[((i-1)^1)+1].flow-=flow; if (maxflow==0) return ans; } return ans; } int dinic() { int ans=0; while (bfs()) { for (int i=1;i<=n;i++) cur[i]=head[i]; ans+=dfs(S,inf); } return ans; } int ans[N*N],pp,id[N],tmp[N]; bool vis[N]; void work(int l,int r) { if (l==r) return ; for (int i=1;i<=tot;i++) edge[i].flow=0; S=id[l],T=id[r]; ans[++pp]=dinic(); bfs(); //标记满流后的残余网络中与S相连的点，实际上当dinic中bfs（）函数变为false时， //在函数中就已经处理了，lev>0的点就是与S相连的点 int ll=l,rr=r; for (int i=l;i<=r;i++) if (lev[id[i]]!=0) tmp[ll++]=id[i]; else tmp[rr--]=id[i]; for (int i=l;i<=r;i++) id[i]=tmp[i]; work(l,ll-1);work(rr+1,r); } int main() { scanf("%d%d",&n,&m); int x,y,w; for (int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&w); addedge(x,y,w); addedge(y,x,w); } for (int i=1;i<=n;i++) id[i]=i; work(1,n); sort(ans+1,ans+pp+1); int t=0; for (int i=1;i<=pp;i++) if (ans[i]!=ans[i-1]) t++; printf("%d",t); return 0; }注意我把数组开小了，然后T了。。。
