マイdinicアルゴリズムネットワークストリーム(詳細な注釈)

/*题目大意:1つの図の中の起点sから終点tまでの最大の流れをsからtまでのすべての経路の中の最大の流量のあの経路の流量の値で割ることを求めます;
(これは簡単そうに見えますが、正直に言うと、この問題は少なくとも30分もかかりました.acの1秒前までは問題の意味が間違っていたのではないかと心配していました)
 
この問題は主に2つの量を要求します:全体の図の最大の流れと1つの経路の最大の流量の値;
 
   
最大ストリームmaxflowは何も言うことはありませんが、直接テンプレートをセットします(しかし、この問題は完全にそのままではいけません.少し修正する必要があります).
私は自分で実現する練習手のつもりだったが、私が手動で実現しようとしたとき、チェン先輩は私に大試合を提案した.
テンプレートはできるだけテンプレートを使うので、そのテンプレートの本を手に入れて、たたいてみると、このテンプレートはよく書けていて、私に叩かせてくれれば、
少なくとも1時間くらいはかかるに違いない!完全なテンプレートのacができない原因は、この問題のhead[i]は-1を格納しているが、テンプレートはそれを0として処理しているためである.
だからテンプレートを修正しました!また、ノックの過程で彼のcur[MAXN]が純粋に空間を浪費していることを発見し、断固として削除!
     
パスの最大流量値maxedgeは、以前チェン先輩が最大パスを求める方法でこの値を求めようとしたが、spafaアルゴリズムを使っているのを見たとき、
私は彼がここで間違っているかもしれないことを知っていたので、彼と討論して、彼も彼のコードを削除して、それから討論して深い検索の方法で求めました.
しかし、環があって、処理が面倒だと感じて、チェンと王相は別の問題を討論して、それから私はまた考えました.
どうして最大のストリームを求めていない时、私のmaxedgeを注入して、それから思い切って打ち鳴らして、1回の短いコードはac! 
最大のネットワークストリームはすでに古典的なテンプレートであり、あまり言う必要はないような気がしますが、テンプレートをセットするだけであれば、
中の仕事の原理を知らないで、正式な試合の中で必要に応じて任意にテンプレートの中の処理の細部を修正するのは難しいです!
だから私はやはり下で大体最大のストリームの1種の比較的に経典を言って、比較的に実用的な1つのネットのストリームのアルゴリズムでしょう
 
   
ステップ1:原点sをルートノードとし、すべてのノードを深さで階層化します(このテンプレートにはbeautifulを比較する場所があります.パス配列psを利用してキューを作成します.
ああ、大きなスペースを節約しました)合流点tが見つかるまで、最後までtが見つからなかったら経路がありません!最大ストリームが完成!
第2部:sから、1層1層下にtを探し、見つけた後、最小容量エッジtrを求め、これを流量として各エッジからtrを減算し、各エッジの逆方向エッジにtrを加える!
第3歩にジャンプする.
       
第3部:f点に遡る(f点はsに最も近い点を満たし、その点を端点とするエッジ容量が0に減らされている);その後第2ステップにジャンプし、tへの経路を探し続ける!tが見つからない場合、
また最初のステップにジャンプします.
注記プロバイダ:GHQ(SpringWater)
  */

#include<stdio.h>
#include<string.h>
#define MAXN 20
#define MAXE 40
#define typec int
const typec inf = 0x3f3f3f3f;
struct edge{int x,y,nxt; typec c;}bf[MAXE];//bf              
int ne,head[MAXN],ps[MAXN],dep[MAXN];
void addedge(int x,int y,typec c)
{
    bf[ne].x=x;bf[ne].y=y;bf[ne].c=c;
    bf[ne].nxt=head[x];head[x]=ne++;
    bf[ne].x=y;bf[ne].y=x;bf[ne].c=0;
    bf[ne].nxt=head[y];head[y]=ne++;
}
typec flow(int n,int s,int t)
{
    typec tr,res=0;
    int i,j,k,l,r,top;
    while(1){
        memset(dep,-1,n*sizeof(int));
        for(l=dep[ps[0]=s]=0,r=1;l!=r;)//      ，dep[i]    i    ，
                                        //   ps[l,r]           l       ，r       ；
        {
            for(i=ps[l++],j=head[i];j!=-1;j=bf[j].nxt)//i             i
            {
                if(bf[j].c&&-1==dep[k=bf[j].y]){//         ，     0，        ！
                    dep[k]=dep[i]+1;ps[r++]=k;
                    if(k==t)//          ，     ，
                    {
                        l=r;
                        break;
                    }
                }
            }
        }
        if(dep[t]==-1)break;//       ，         ，       ！

        for(i=s,top=0;;)
        {
            if(i==t)//       ，   t，    s t        tr，      tr，     tr
            {
                for(k=0,tr=inf;k<top;++k)//          ps[top] ，
                    if(bf[ps[k]].c<tr)tr=bf[ps[l=k]].c; //      tr，      l=k，l     ps【l】
                                                        //       t          tr 0  bf[ps[l]].x，      ！
                    for(k=0;k<top;++k)//    tr，    tr
                        bf[ps[k]].c-=tr,bf[ps[k]^1].c+=tr;
                    res+=tr;i=bf[ps[top=l]].x;//   res+tr，         ，       i
            }
            for(j=head[i];j!=-1;j=bf[j].nxt)//    i         bf[j].y
                if(bf[j].c&&dep[i]+1==dep[bf[j].y])break;
            if(j!=-1)//           ，        ，    i        bf[j].y，  j     ps   
            {
                ps[top++]=j;// j     ps   
                i=bf[j].y;//   i        bf[j].y
            }
            else//    i ，        ，     
            {
                if(!top)break;//     top==0 ，  i==s ，    ！
                dep[i]=-1;i=bf[ps[--top]].x;//        ，     i          ，
                                            //  dep[i]  （dep[i]=-1）,     bf[ps[--top]].x    i！
            }
        }
    }
    return res;
}
int main()
{
    int T,cas,e,s,t,n,maxflow,i;
    int x,y,c;
    double ans;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d%d%d",&cas,&n,&e,&s,&t);
        memset(head,-1,sizeof(head));
        for(i=ne=0;i<e;i++)
        {
            scanf("%d%d%d",&x,&y,&c);
            addedge(x,y,c);
        }
        maxedge=0;
        maxflow=flow(n,s,t);
        
        ans=(double)maxflow/(double)maxedge;
        printf("%d %0.3lf
",cas,ans);
        
    }
    return 0;
}