最大流模闆更新(Dinic)...POJ-1273

      明天就要出發去武漢了..剛才更新了下最大流的模闆...較之以前的代碼..本次更新主要是兩方面...

     1.連結清單存邊采取存2*M邊,也就是在讀入時就将其反向邊開在相鄰的位置..那麼在做剩餘網絡時就能直接用了..省空間省時間..

     2.DFS當找到一條增廣路後..回朔到一個還剩了流量的位置..這使得BFS每次對點分一次層,都最大限度的利用完..真正展現出Dinic的優勢..

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
#define oo 2000000000
#define ll long long
using namespace std;
struct node
{
       int x,y,c,next;
}line[405];
int n,m,_link[205],ans,dis[205],num,way[205],Flow[205];
queue<int> myqueue;
bool BFS()
{
       int h,i,k;
       memset(dis,0,sizeof(dis));
       dis[1]=1;
       while (!myqueue.empty()) myqueue.pop();
       myqueue.push(1);
       while (!myqueue.empty())
       {
              h=myqueue.front();
              myqueue.pop();
              k=_link[h];
              while (k)
              {
                    if (line[k].c && !dis[line[k].y])
                    {
                           dis[line[k].y]=dis[h]+1;
                           myqueue.push(line[k].y);
                    }
                    k=line[k].next;
              }
       }
       return dis[n];
}
void DFS(int h)
{
       int k;
       if (h==n)
       {
             ans+=Flow[num];
             for (h=1;h<=num;h++)
             {
                    line[way[h]].c-=Flow[num];
                    Flow[h]-=Flow[num];
                    if (way[h]%2) k=way[h]+1;
                        else k=way[h]-1;
                    line[k].c+=Flow[num];
             }
             return;
       }
       k=_link[h];
       num++;
       while (k)
       {
             if (line[k].c && dis[line[k].y]-dis[h]==1)
             {
                    way[num]=k;
                    Flow[num]=min(line[k].c,Flow[num-1]);
                    DFS(line[k].y);
                    if (!Flow[num-1]) 
                    {
                            num--;
                            return; 
                    }
             }
             k=line[k].next;
       }
       num--;
       return;
}
void Dinic()
{
       ans=0; 
       while (BFS())
       {
             num=0;
             Flow[0]=oo;
             DFS(1);
       }
       return;
}
int main()
{      
       int i,x,y,z;
       while (~scanf("%d%d",&m,&n))
       {
              memset(_link,0,sizeof(_link));
              memset(line,0,sizeof(line)); 
              for (i=1;i<=m;i++)
              {
                     scanf("%d%d%d",&x,&y,&z);
                     line[i*2-1].next=_link[x];
                     _link[x]=i*2-1;
                     line[i*2-1].x=x; line[i*2-1].y=y;
                     line[i*2-1].c=z;
                     line[i*2].next=_link[y];
                     _link[y]=i*2;
                     line[i*2].x=y; line[i*2].y=x;
                     line[i*2].c=0;
              }
              Dinic();
              printf("%d\n",ans);
       }
       return 0;
}