题意弄了半天：
给出一个有向图，带边权，src,dst. 求出src到dst的最大流，再求出从src到dst流量最大的路径的流量，求它们的比值。
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define oo 0x3f3f3f3f
#define maxn 1010
using namespace std; struct Edge {
int u, v, f, cap;
Edge( int u, int v, int f, int cap ):u(u),v(v),f(f),cap(cap){}
};
struct Dinic {
int n, src, dst;
vector<Edge> edge;
vector<int> g[maxn];
int dep[maxn], cur[maxn], sig; void init( int n, int src, int dst ) {
this->n = n;
this->src = src;
this->dst = dst;
for( int u=; u<=n; u++ )
g[u].clear();
edge.clear();
}
void add_edge( int u, int v, int f ) {
g[u].push_back( edge.size() );
edge.push_back( Edge(u,v,f,f) );
g[v].push_back( edge.size() );
edge.push_back( Edge(v,u,,f) );
}
bool bfs() {
queue<int> qu;
memset( dep, , sizeof(dep) );
qu.push( src );
dep[src] = ;
while( !qu.empty() ) {
int u=qu.front();
qu.pop();
for( int t=; t<g[u].size(); t++ ) {
Edge &e = edge[g[u][t]];
if( e.f && !dep[e.v] ) {
dep[e.v] = dep[e.u]+;
qu.push( e.v );
}
}
}
return dep[dst];
}
int dfs( int u, int a, int minc ) {
if( u==dst || a== ) {
sig = max( minc, sig );
return a;
}
int remain=a, past=, na;
for( int &t=cur[u]; t<g[u].size(); t++ ) {
Edge &e = edge[g[u][t]];
Edge &ve = edge[g[u][t]^];
if( dep[e.v]==dep[e.u]+ && (na=dfs(e.v,min(remain,e.f),min(minc,e.cap))) ) {
remain -= na;
past += na;
e.f -= na;
ve.f += na;
if( remain== ) break;
}
}
return past;
}
void maxflow( int &tot, int &sig ) {
tot = sig = ;
this->sig = ;
while( bfs() ) {
memset( cur, , sizeof(cur) );
tot += dfs(src,oo,oo);
}
sig = this->sig;
}
}; int n, m;
Dinic D;
int main() {
int T;
scanf( "%d", &T );
while( T-- ) {
int cas, src, dst;
scanf( "%d%d%d%d%d", &cas, &n, &m, &src, &dst );
src++, dst++;
D.init( n, src, dst );
for( int i=,u,v,w; i<=m; i++ ) {
scanf( "%d%d%d", &u, &v, &w );
u++, v++;
D.add_edge( u, v, w );
}
int tot, sig;
D.maxflow( tot, sig );
printf( "%d %.3lf\n", cas, double(tot)/double(sig) );
}
}