原题地址：http://poj.org/problem?id=2455
题目大意：给出一个N个点的无向图，中间有P条边，要求找出从1到n的T条通路，满足它们之间没有公共边，并使得这些通路中经过的最长的边的长度最短。两点之间允许有重边
数据范围：2 <= N <= 200， 1 <= P <= 40,000，1 <= T <= 200，1 <= 每条路的长度L <= 1,000,000
题目分析：
看到“最大值最小”的第一反应就是二分最大长度k，满足T条通路没有公共边的第一反应就是将每条边的容量赋为1然后跑一遍最大流。这样算法就出来了：读入并建图，二分最大长度k，将所有长度小于等于 k 的边的容量设为1， 大于 k 的边容量设为0，然后以1为源点，n为汇点做一遍最大流，如果满足最大流大于等于T，则合要求继续二分，直至找出答案。
一开始在双向边建图的时候有点犹豫。毕竟网络流要求每条边必须要有反向边。最开始的想法是将每条双向边都拆成两条单向边，对每条单向边都建立一条长度为无穷大的反向边（无穷大是为了保证二分时赋初始容量都将它们为0），但是后来证明这种想法是错误的：因为题目要求每条边只能走一次，但是按我的想法每条边可以正向走一次，反向走一次，加上题目中允许有重边，就使情况变得更加复杂。后来我发现网络流的反向边不一定要初始容量为0——就算我将这一条双向边的两个方向按照网络流的一对反向边来建立，初始容量都允许为1，无论正着流还是反着流这条边所能允许的总容量必然只有0或1……然后就想通了（希望能给这里想不太清楚的同学们一点帮助）
然后这道题TLE到死……经过hockey指点才发现是我Dinic 写残了，应该到不能流的时候就退出但是我没有……改掉这一点之后，我加上当前弧优化的Dinic还是可以600+MS勉强AC的
PS：网上有些人说重新建立源点和汇点，并连接一条从源点到1的容量为T的边，其实丝毫没有必要，直接以1为源点是可以的
//date 20140118
#include <cstdio>
#include <cstring> const int maxn = ;
const int maxm = ;
const int INF = 0x7FFFFFFF; inline int getint()
{
int ans(); char w = getchar();
while('' > w || w > '')w = getchar();
while('' <= w && w <= '')
{
ans = ans * + w - '';
w = getchar();
}
return ans;
} inline int min(int a, int b){return a < b ? a : b;}
inline int max(int a, int b){return a > b ? a : b;} int n, m, T;
int s, t;
struct edge
{
int v, w, c, next;
}E[maxm];
int a[maxn];
int now[maxn];
int nedge;
int lab[maxn]; inline void add(int u, int v, int w, int c)
{
E[++nedge].v = v;
E[nedge].c = c;
E[nedge].w = w;
E[nedge].next = a[u];
a[u] = nedge;
} int maxl, minl; inline int label()
{
static int q[maxn];
int l = , r = ;
memset(lab, 0xFF, sizeof lab);
q[] = s; lab[s] = ;
while(l < r)
{
int x = q[++l];
for(int i = a[x]; i; i = E[i].next)
if(E[i].c == && lab[E[i].v] == -)
{
lab[E[i].v] = lab[x] + ;
q[++r] = E[i].v;
}
}
return lab[t] != -;
} int Dinic(int v, int f)
{
if(v == t)return f;
int res = , w;
for(int i = now[v]; i; i = now[v] = E[i].next)
if((E[i].c == ) && (f > ) && (lab[v] + == lab[E[i].v]) && (w = Dinic(E[i].v, min(f, E[i].c))))
{
E[i].c -= w;
E[i ^ ].c += w;
f -= w;
res += w;
if(f == )break;
}
if(res == )lab[v] = -;
return res;
} inline int max_flow()
{
int ans = ;
while(label())
{
for(int i = s; i <= t; ++i)now[i] = a[i];
ans += Dinic(s, INF);
}
return ans;
} inline bool check(int k)
{
for(int i = ; i <= nedge; i += )
if(E[i].w <= k)E[i].c = E[i ^ ].c = ; else E[i].c = E[i ^ ].c = ;
int ans = max_flow();
//printf("%d\n", ans);
return ans >= T;
} inline int solve(int l, int r)
{
int mid;
while(l < r)
{
mid = (l + r) >> ;
if(check(mid))r = mid;
else l = mid + ;
}
return l;
} int main()
{
n = getint(); m = getint(); T = getint();
nedge = ; maxl = ; minl = INF;
s = ; t = n;
int x, y, z;
for(int i = ; i <= m; ++i)
{
x = getint(); y = getint(); z = getint();
add(x, y, z, );
add(y, x, z, );
maxl = max(maxl, z);
minl = min(minl, z);
}
int ans = solve(minl, maxl);
printf("%d\n", ans);
return ;
}
小结：建图还是需要多加思考多加练习，代码模板也是需要不断完善的，加油~