这两题本质是一致的；
一般来说，对于最长（短）化最短（长）的问题我们一般都使用二分答案+判定是否可行
因为这样的问题，我们一旦知道答案，就能知道全局信息
拿poj2455举例，对于二分出的一个答案，我们将不符合的边全部去掉，在做一遍最大流判断是否成立即可
注意这道题有重边，所以用链式前向星比较好（TT，当时我用的数组模拟邻接表表不要太烦）
type node=record
po,flow,cost:longint;
end;
var w,ow:array[..,..] of node;
cur,pre,numh,h,s,s0:array[..] of longint;
ans,max,mid,l,r,x,y,z,i,n,m,p:longint; procedure add(x,y,z,f:longint); //很繁琐的结构，需要检查好久，重边优先选择链式前向星，比较方便
begin
inc(s[x]);
w[x,s[x]].po:=y;
w[x,s[x]].cost:=z;
w[x,s[x]].flow:=f;
end; function maxflow(k:longint):boolean; //很喜欢写sap，判定
var j,sum,u,i,t,r,tmp:longint;
begin
max:=-;
fillchar(pre,sizeof(pre),);
fillchar(cur,sizeof(cur),);
fillchar(h,sizeof(h),);
fillchar(numh,sizeof(numh),); //一定要注意，这句话没有不影响程序结果，但会拖慢程序速度（相当于没用到GAP优化），谨记
fillchar(s0,sizeof(s0),);
for i:= to n do
for j:= to s[i] do
begin
if w[i,j].cost<=k then //根据条件构造新图
begin
inc(s0[i]);
ow[i,s0[i]]:=w[i,j];
end;
end;
numh[]:=n;
sum:=;
u:=;
while h[]<n do
begin
if u=n then
begin
i:=;
while i<>n do
begin
t:=cur[i];
if max<ow[i,t].cost then max:=ow[i,t].cost; //小优化而已，在最大流里面找一条最大的边，实际上答案是这个
dec(ow[i,t].flow);
i:=ow[i,t].po;
end;
inc(sum);
if sum=p then exit(true);
u:=;
end;
r:=-;
for i:= to s0[u] do
if (ow[u,i].flow>) and (h[u]=h[ow[u,i].po]+) then
begin
r:=i;
break;
end; if r<>- then
begin
cur[u]:=r;
pre[ow[u,r].po]:=u;
u:=ow[u,r].po;
end
else begin
dec(numh[h[u]]);
if numh[h[u]]= then exit(false);
tmp:=n; //注意这里千万不要顺手打成maxlongint之类
for i:= to s0[u] do
if (ow[u,i].flow>) and (tmp>h[ow[u,i].po]) then tmp:=h[ow[u,i].po];
h[u]:=tmp+;
inc(numh[h[u]]);
if u<> then u:=pre[u];
end;
end;
exit(false);
end; begin
readln(n,m,p);
for i:= to m do
begin
readln(x,y,z);
add(x,y,z,);
add(y,x,z,);
if z>r then r:=z;
end;
l:=;
while l<=r do
begin
mid:=(l+r) shr ;
if maxflow(mid) then
begin
ans:=max; //小小的优化，但不是所有二分判定都可以用
r:=max-;
end
else l:=mid+;
end;
writeln(ans);
end.
poj2391也是一样的，只不过多了floyd预处理
一般的，对于答案越大，决策就越有可能成功的这类具有单调性的题目，通常使用二分答案