最小割1
概述
在最大流的定理我们证明了在最大流没有增广路，同时如果割的流量等于它的容量那么这个流是最大流。因此可以得出最大流是最小割。直接用dinic模板去求即可，然后如果从s点可以遍历到的点即为S集合，否则为T集合。
例题
给出一个带权无向图 G=(V,E)G=(V,E)，每条边 e有一个权 we。
求将点 s 和点 t 分开的一个边割集 C，使得该割集的平均边权最小，即最小化：
∑（e∈C）we / |C|
注意： 边割集的定义与最小割中的割边的集合不同。在本题中，一个边割集是指：将这些边删去之后，ss 与 tt 不再连通。
输入格式
第一行包含四个整数 n,m,s,tn,m,s,t，其中 n,m 分别表示无向图的点数、边数。
接下来 mm 行，每行包含三个整数 a,b,w，表示点 a和 b 之间存在一条无向边，边权为 w。
点的编号从 1 到 n。
输出格式
输出一个实数，表示将点 s 和点 t 分开的边割集的最小平均边权。
结果保留两位小数。
先使用01分数规划做一个处理得到：∑（e∈C）（We - g）要证明这一部分最小值，直接使用二分去判断是否满足g；所以求当前图里的最小值，在每一次建图的时候，因为要使值最小，我们可以先把每一条边的容量-g，如果小于0那么我们直接选取这一条边即可，如果大于0，我们肯定只选择ST之间的容量，那么就是最小割。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110,M=810;
const double eps=1e-8,inf=1e8;
int n,m,S,T;
int head[N],idx;
int cur[N],q[N],d[N];
struct Edge{
int next,to,w;
double f;
}edge[M];
void add(int a,int b,int c)
{
edge[idx]=(Edge){head[a],b,c,0},head[a]=idx++;
edge[idx]=(Edge){head[b],a,c,0},head[b]=idx++;
}
bool bfs()
{
int hh=0,tt=0;
memset(d,-1,sizeof d);
q[0]=S,d[S]=0,cur[S]=head[S];
while(hh<=tt)
{
int t=q[hh++];
for(int i=head[t];~i;i=edge[i].next)
{
int ver=edge[i].to;
if(d[ver]==-1&&edge[i].f>0)
{
d[ver]=d[t]+1;
cur[ver]=head[ver];
if(ver==T) return true;
q[++tt]=ver;
}
}
}
return false;
}
double find(int u,double limit)
{
if(u==T) return limit;
double flow=0;
for(int i=cur[u];~i&&flow<limit;i=edge[i].next)
{
cur[u]=i;
int ver=edge[i].to;
if(d[ver]==d[u]+1&&edge[i].f>0)
{
double t=find(ver,min(edge[i].f,limit-flow));
if(t<eps) d[ver]=-1;
edge[i].f-=t,edge[i^1].f+=t,flow+=t;
}
}
return flow;
}
double dinic(double mid)
{
double res=0;
for(int i=0;i<idx;i+=2)
if(edge[i].w<=mid) {
res+=edge[i].w-mid;
edge[i].f=edge[i^1].f=0;
}
else edge[i].f=edge[i^1].f=edge[i].w-mid;
double r=0,flow;
while(bfs())
while(flow=find(S,inf))
r+=flow;
return r+res;
}
int main()
{
memset(head,-1,sizeof head);
scanf("%d%d%d%d",&n,&m,&S,&T);
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
double l=0,r=1e7;
while(r-l>eps)
{
double mid=(l+r)/2;
if(dinic(mid)<eps) r=mid;
else l=mid;
}
printf("%.2lf\n",r);
return 0;
}
