题目大意：
给出一张无向图，找出T条从1..N的路径，互不重复，求走过的所有边中的最大值最小是多少。
算法讨论：
首先最大值最小就提醒我们用二分，每次二分一个最大值，然后重新构图，把那些边权符合要求的边加入新图，在新图上跑网络流。
这题有许多注意的地方：
1、因为是无向图，所以我们在加正向边和反向边的时候，流量都是1，而不是正向边是1，反向边是0。
2、题目中说这样的路径可能不止t条，所以我们在最后二分判定的时候不能写 == t，而是要 >= t。
3、这题很容易T ，表示我T了N遍，弱菜啊。
Codes：
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue> using namespace std; struct Edge{
int from, to, cap, flow;
Edge(int _from = , int _to = , int _cap = , int _flow = ):
from(_from), to(_to), cap(_cap), flow(_flow) {}
}E[ + ]; struct Dinic{
static const int N = + ;
static const int M = + ;
static const int oo = 0x3f3f3f3f; int n, m, s, t;
vector <Edge> edges;
vector <int> G[N];
int dis[N], cur[N];
bool vi[N]; void Clear(){
for(int i = ; i <= n; ++ i) G[i].clear();
edges.clear();
} void Add(int from, int to, int cap, int flow){
edges.push_back((Edge){from, to, cap, });
edges.push_back((Edge){to, from, cap, });
int m = edges.size();
G[from].push_back(m - );
G[to].push_back(m - );
} bool bfs(){
for(int i = ; i <= n; ++ i) vi[i] = false;
dis[s] = ; vi[s] = true;
queue <int> q; q.push(s); while(!q.empty()){
int x = q.front(); q.pop();
for(int i = ; i < G[x].size(); ++ i){
Edge &e = edges[G[x][i]];
if(!vi[e.to] && e.cap > e.flow){
vi[e.to] = true;
dis[e.to] = dis[x] + ;
q.push(e.to);
}
}
}
return vi[t];
} int dfs(int x, int a){
if(x == t || a == ) return a;
int flw = , f;
for(int &i = cur[x]; i < G[x].size(); ++ i){
Edge &e = edges[G[x][i]];
if(dis[x] + == dis[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > ){
e.flow += f; edges[G[x][i]^].flow -= f;
a -= f; flw += f;
if(!a) break;
}
}
return flw;
} int Maxflow(int s, int t){
this->s = s;this-> t = t;
int flw = ;
while(bfs()){
memset(cur, , sizeof cur);
flw += dfs(s, oo);
}
return flw;
} }Net; int ns, ps, ts;
int l = 0x3f3f3f3f, r, mid; bool check(int mv){
for(int i = ; i < ps; ++ i){
if(E[i].cap <= mv){
Net.Add(E[i].from, E[i].to, , );
}
}
return Net.Maxflow(, Net.n) >= ts;
} int Solve(){
int ans; while(l <= r){
Net.Clear();
mid = l + (r - l) / ;
if(check(mid)){
ans = mid; r = mid - ;
}
else l = mid + ;
} return ans;
} int main(){
int x, y, z; scanf("%d%d%d", &ns, &ps, &ts);
Net.n = ns;
for(int i = ; i < ps; ++ i){
scanf("%d%d%d", &x, &y, &z);
E[i] = (Edge){x, y, z, };
l = min(l, z); r = max(r, z);
} printf("%d\n", Solve());
return ;
}
POJ 2455
让人更加不能理解的是，为什么我换了上面的邻接表的形式，用STL容器来存邻接表就AC，用数组来存就T成狗。
下面是我狂T的代码，良心网友们给查查错误呗。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue> using namespace std; int ns, ps, ts, te;
int l=0x3f3f3f3f, r, Mid; struct Edge{
int from, to, dt;
}e[ + ]; struct Dinic{
static const int maxn = + ;
static const int maxm = + ;
static const int oo = 0x3f3f3f3f; int n,m,s,t;
int tot;
int first[maxn],next[maxm];
int u[maxm],v[maxm],cap[maxm],flow[maxm];
int cur[maxn],dis[maxn];
bool vi[maxn]; Dinic(){tot=;memset(first,-,sizeof first);}
void Clear(){tot = ;memset(first,-,sizeof first);}
void Add(int from,int to,int cp,int flw){
u[tot] = from;v[tot] = to;cap[tot] = cp;flow[tot] = ;
next[tot] = first[u[tot]];
first[u[tot]] = tot;
++ tot;
}
bool bfs(){
memset(vi,false,sizeof vi);
queue <int> q;
dis[s] = ;vi[s] = true;
q.push(s); while(!q.empty()){
int now = q.front();q.pop();
for(int i = first[now];i != -;i = next[i]){
if(!vi[v[i]] && cap[i] > flow[i]){
vi[v[i]] = true;
dis[v[i]] = dis[now] + ;
q.push(v[i]);
}
}
}
return vi[t];
}
int dfs(int x,int a){
if(x == t || a == ) return a;
int flw=,f;
int &i = cur[x];
for(i = first[x];i != -;i = next[i]){
if(dis[x] + == dis[v[i]] && (f = dfs(v[i],min(a,cap[i]-flow[i]))) > ){
flow[i] += f;flow[i^] -= f;
a -= f;flw += f;
if(a == ) break;
}
}
return flw;
}
int MaxFlow(int s,int t){
this->s = s;this->t = t;
int flw=;
while(bfs()){
memset(cur,,sizeof cur);
flw += dfs(s,oo);
}
return flw;
}
}Net; bool check(int mid){
Net.Clear();
for(int i = ; i <= ps; ++ i){
if(e[i].dt <= mid){
Net.Add(e[i].from, e[i].to, , );
Net.Add(e[i].to, e[i].from, , );
}
}
return Net.MaxFlow(, Net.n) >= ts;
}
int Solve(){
int ans;
while(l <= r){
Mid = l + (r - l) / ;
if(check(Mid)){
ans = Mid; r = Mid - ;
}
else l = Mid + ;
}
return ans;
}
int main(){
int x, y, z;
scanf("%d%d%d", &ns, &ps, &ts);
Net.n = ns;te = ;
for(int i = ; i <= ps; ++ i){
scanf("%d%d%d", &x, &y, &z);
++ te;
e[te].from = x;e[te].to = y;e[te].dt = z;
l = min(l, z); r = max(z, r);
}
printf("%d\n", Solve());
return ;
}
POJ 2455 T 版