/***********************
*  POJ-1273
*  Ford-Fulkerson
***********************/
#include <stdio.h>#include <string.h>const int INF = (1<<31)-1;int map[500][500];//邻接矩阵 int fa[500];//记录父节点 int vis[500];//DFS标记数组 int dfs(int stap,int min);int n,m;int main(){        while (scanf("%d%d",&m,&n)!=EOF){                memset(map,0,sizeof(map));        for (int i=1;i<=m;i++){            int u,v,val;            scanf("%d%d%d",&u,&v,&val);            map[u][v] += val;//累加处理,防止重边         }                int max_flow = 0;        int temp;                while (1){                        memset(vis,0,sizeof(vis));            vis[1] = 1;            for (int i=1;i<=n;i++) fa[i] = i;                        temp = dfs(1,INF);//从顶点[1]出发,在残留图中DFS搜索一条增广路,返回路径的合法流量             if (temp == INF) break;//如果搜不到增广路则说明已经没有更大流量            max_flow += temp;                        //更新残留图,正向边减去temp,反向边加上temp             int p = n;            while (p!=1){                int fat = fa[p];                map[fat][p] -= temp;                map[p][fat] += temp;                p = fat;            }                    }        printf("%d\n",max_flow);    }    return 0;}int dfs(int stap,int min){        for (int i=1;i<=n;i++)//寻找stap所指向的一个子节点     if (!vis[i]&&map[stap][i]>0){                vis[i] = 1;        fa[i] = stap;                if (map[stap][i]<min) min = map[stap][i];//保持流量合法         if (i==n) return min;//DFS出口         else{            int temp = dfs(i,min);            if (temp<min) min = temp;        }    }        if (fa[n]!=n) return min;//fa[n]!=n 说明本次搜素成功地找到一条增广路     else return INF;}

#include <stdio.h>
#include <string.h>
#include <queue>using namespace std;const int INF = (1<<31)-1;const int MAX = 1001;int map[MAX][MAX];//记录残留图int org[MAX][MAX];//记录原图int head[MAX];int next[MAX*2];int edge[MAX*2];int fa[MAX];int vis[MAX];//vis数组同时用作标记和记录源点到本节点的合法流量int main(){        int n,m,sta,end;    int t,cases;    scanf("%d",&t);    while (t--){                int u,v,val;        scanf("%d%d%d%d%d",&cases,&n,&m,&sta,&end);        sta++;end++;        memset(map,0,sizeof(map));        memset(org,0,sizeof(org));        memset(head,0xff,sizeof(head));        int cnt = 0;                for(int i=1;i<=m;i++){            scanf("%d%d%d",&u,&v,&val);            map[u+1][v+1] += val;            org[u+1][v+1] += val;                        cnt++;            edge[cnt] = v+1;            next[cnt] = head[u+1];            head[u+1] = cnt;                        cnt++;            edge[cnt] = u+1;            next[cnt] = head[v+1];            head[v+1] = cnt;        }                int max_flow = 0;        int max_rot = 0;                while (1){                        for (int i=1;i<=n;i++) fa[i] = i;            memset(vis,0,sizeof(vis));            vis[sta] = INF;            queue<int> q;            q.push(sta);            while (!q.empty()){                u = q.front();                q.pop();                for (int i=head[u];i!=-1;i=next[i]){                    v = edge[i];                    if (!vis[v]&&map[u][v]){                        q.push(v);                        fa[v] = u;                        vis[v] = vis[u]<map[u][v] ? vis[u]:map[u][v];                        if (v==end) break;                    }                }                if (v==end) break;            }                        if (vis[end]==0) break;            max_flow += vis[end];            int p = end;            int rot_min = INF;            while (p!=sta){                int fat = fa[p];                if (org[fat][p]<rot_min) rot_min = org[fat][p];                map[fat][p] -= vis[end];                map[p][fat] += vis[end];                p = fat;            }                        if (rot_min>max_rot) max_rot = rot_min;        }                double ans = ((double)max_flow)/((double)max_rot);        printf("%d %.3lf\n",cases,ans);            }        return 0;}