神奇的上下界网络流----- （总结by ： becauseofyou）(四)
;
while(l <= r)
{
int mid = l + r >> 1;
Map_Init(mid);
int tmp = SAP(S,T,n);
if(tmp == max_flow)
{
ans1 = mid;
r = mid - 1;
}
else
{
l = mid + 1;
}
}
}
bool map_init(int mid)//mid 为下界
{
init();
memset(in,0,sizeof(in));
for(int i = 0; i < m; i++)
{
if(c[i] < mid) return false;
add_edge(u[i],v[i],c[i]-mid,0);
in[v[i]] += mid;
in[u[i]] -= mid;
}
return true;
}
bool ok(int mid)
{
int i , j;
if(!map_init(mid)) return false;
int ss = n , tt = n + 1;
for(i = 0; i < n ; i++)
{ www.2cto.com
if(in[i] > 0) add_edge(ss,i,in[i],0);
if(in[i] < 0) add_edge(i,tt,-in[i],0);
}
add_edge(T,S,INF,0);
SAP(ss,tt,tt+1);
for(i = head[ss];i!=-1;i=edge[i].next)
{
if(edge[i].c) return false;
}
return SAP(S,T,tt+1) == max_flow;
}
void question2() // 二分下界
{
int l = 0 , r = maxc ;// 理论上讲这个r赋为minc是可以的，但是WA了（因为如果大于minc就一定会有边的上界小于下界）
while(l <= r)
{
int mid = l + r >> 1;
if(ok(mid))
{
ans2 = mid;
l = mid + 1;
}
else
{
r = mid - 1;
}
}
}
int main()
{
int t,i,j,k;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d%d",&n,&m,&S,&T,&P);
init();
maxc = 0;
minc = INF;
for(i=0;i
{
scanf("%d%d%d",&u[i],&v[i],&c[i]);
add_edge(u[i],v[i],c[i],0);
if(c[i] > maxc) maxc = c[i];
if(c[i] < minc) minc = c[i];
}
max_flow = SAP(S,T,n);
question1();
question2();
printf("%lld %lld\n",(lld)ans1*P,(lld)ans2*P);
}
return 0;
}
/*
100
4 3 0 3 3
0 1 2
1 2 3
2 3 4
4 5 0 3 2
0 1 2
0 2 1
1 2 1
1 3 1
2 3 2
4 5 0 3 2
0 1 1
0 2 1
1 2 2
1 3 2
2 3 1
5 5 0 4 1
0 3 1
0 2 1
3 1 1
2 1 1
1 4 1
6 6
4 2
2 0
1 0
*/
最后再总结一下建图方法，方便现场赛可以快速的回忆起来。
1：无源汇的可行流 ： 新建源点，汇点，M[i]为每个点进来的下界流减去出去的下界流，如果M[i]为正，由源点向改点建M[i]的边，反之，由该点向汇点建M[i]的边，原图中的边为每条边的上界建去下界。跑一遍最大流，每条边的流量加上下界流就是答案。
2：有源汇的最大流： 从汇点向源点建一条容量为INF的边，用上面的方法判断是否有解，有解就再跑一遍从原图中源点到汇点的最大流
3：有源汇的最小流：先跑一遍最大流，然后连上从汇点到源点的边，再按照1的方法做就好了