高效的最大流sap+邻接表模版

/*
最大流模板
isap复杂度(v^2*e)
*/
/*
*State: HDU4280 3609MS 8860K 3571 B C++
*题目大意：
*  有N个岛屿 M条无向路 每个路有一最大允许的客流量，求从最西的那个岛屿最多能运
*  用多少乘客到最东的那个岛屿。
*解题思路：
*  很单纯的网络流，重点是卡时间 模板的高效性很重要啊该模板详解
*  参见这里  模板题就不注释了
*解题感想：
*  10000ms的时间里，大多数最大流算法都挂掉了，就这个坚持下来了，用了3000ms左右。
*/

#include 
#include 
#include 
#define VM 100010
#define EM 400010

using namespace std;
const int inf = 0x3f3f3f3f;

struct E
{
    int to, frm, nxt, cap;
}edge[EM];

int head[VM], e;//建图时初始化
int dep[VM], gap[VM];//ISAP函数内初始化

void init()
{
 e = 0;
 memset(head, -1, sizeof(head));
}

void addEdge(int cu, int cv, int cw)
{
    edge[e].frm = cu;
    edge[e].to = cv;
    edge[e].cap = cw;
    edge[e].nxt = head[cu];
    head[cu] = e++;

    edge[e].frm = cv;
    edge[e].to = cu;
    edge[e].cap = 0;
    edge[e].nxt = head[cv];
    head[cv] = e++;
}

int que[VM];

void BFS(int des)
{
    memset(dep, -1, sizeof(dep));
    memset(gap, 0, sizeof(gap));
    gap[0] = 1;
    int front = 0, rear = 0;
    dep[des] = 0;
    que[rear++] = des;
    int u, v;
    while (front != rear)
    {
        u = que[front++];
        front = front%VM;
        for (int i=head[u]; i!=-1; i=edge[i].nxt)
        {
            v = edge[i].to;
            if (edge[i].cap != 0 || dep[v] != -1)
                continue;
            que[rear++] = v;
            rear = rear % VM;
            ++gap[dep[v] = dep[u] + 1];
        }
    }
}

int cur[VM], stack[VM];
//sap模板
int ISAP(int src, int des, int n)//源点、汇点、图中点的总数      
{
    int res = 0;
    BFS(des);
    int top = 0;
    memcpy(cur, head, sizeof(head));
    int u = src, i;
    while (dep[src] < n)
    {
        if (u == des)
        {
            int temp = inf, inser = n;
            for (i=0; i!=top; ++i)
                if (temp > edge[stack[i]].cap)
                {
                    temp = edge[stack[i]].cap;
                    inser = i;
                }
            for (i=0; i!=top; ++i)
            {
                edge[stack[i]].cap -= temp;
                edge[stack[i]^1].cap += temp;
            }
            res += temp;
            top = inser;
            u = edge[stack[top]].frm;
        }

        if (u != des && gap[dep[u] -1] == 0)
            break;
        for (i = cur[u]; i != -1; i = edge[i].nxt)
            if (edge[i].cap != 0 && dep[u] == dep[edge[i].to] + 1)
                break;

        if (i != -1)
        {
            cur[u] = i;
            stack[top++] = i;
            u = edge[i].to;
        }
        else
        {
            int min = n;
            for (i = head[u]; i != -1; i = edge[i].nxt)
            {
                if (edge[i].cap == 0)
                    continue;
                if (min > dep[edge[i].to])
                {
                    min = dep[edge[i].to];
                    cur[u] = i;
                }
            }
            --gap[dep[u]];
            ++gap[dep[u] = min + 1];
            if (u != src)
                u = edge[stack[--top]].frm;
        }
    }
    return res;
}

int main()
{
#ifndef ONLINE_JUDGE
 freopen("in.txt", "r", stdin);
#endif

    int n, m, T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d %d", &n, &m);
        int x, y, src, des;
        int Min = inf, Max = -inf;
        for (int i = 1; i <= n; ++i)       //找出起点src 终点des
        {
            scanf("%d %d", &x, &y);
            if (x <= Min)
            {
                src = i;
                Min = x;
            }
            if (x >= Max)
            {
                des = i;
                Max = x;
            }
        }

  init();
        int u, v, c;
        for (int i = 0; i != m; ++i)
        {
            scanf("%d %d %d", &u, &v, &c);
            addEdge(u, v, c);
            addEdge(v, u, c);
        }
        int ans = ISAP(src, des, n);
        printf("%d\n", ans);
    }
    return 0;
}

//Isap邻接矩阵版模板
//HDU3549 Isap邻接矩阵版
//46ms
#include 
#include 
#include 

#define M 16
using namespace std;

const int inf = 0x3f3f3f3f;

int maze[M][M];
int gap[M],dis[M],pre[M],cur[M];
void init()
{
 memset(maze, 0, sizeof(maze));
}

//起点是0， 终点是n-1,nodenum为点的个数
int ISAP(int s, int t, int nodenum) {

 memset(cur, 0, sizeof(cur));
 memset(dis, 0, sizeof(dis));
 memset(gap, 0, sizeof(gap));

 int u = pre[s] = s,maxflow = 0,aug = inf;
 gap[0] = nodenum;
 while(dis[s] < nodenum) {
loop:  
   for(int v = cur[u]; v < nodenum; v++) if(maze[u][v] && dis[u] == dis[v] + 1) {
   aug = min(aug, maze[u][v]);
   pre[v] = u;
   u = cur[u] = v;
   if(v == t) {
    maxflow += aug;
    for(u = pre[u];v != s;v = u,u = pre[u]) {
     maze[u][v] -= aug;
     maze[v][u] += aug;
    }
    aug = inf;
   }
   goto loop;
  }
  int mindis= nodenum-1;
  for(int v = 0; v < nodenum; v++) if(maze[u][v] && mindis> dis[v]) {
   cur[u] = v;
   mindis= dis[v];
  }
  if((--gap[dis[u]])== 0)    break;
  gap[dis[u] = mindis+1] ++;
  u = pre[u];
 }
 return maxflow;
}

int main(void)
{
#ifndef ONLINE_JUDGE
 freopen("HDU3549.txt", "r", stdin);
#endif

 int n, m, cas, cas_c = 1;
 scanf("%d", &cas);
 while(cas--)
 {
  scanf("%d %d", &n, &m);
  init();
  int u, v, w;
  for(int i = 0; i < m; i++)
  {
   scanf("%d %d %d", &u, &v, &w);
   u--, v--;
   maze[u][v] += w;
  }
  int sol = ISAP(0, n-1, n);//起点，终点
  printf("Case %d: %d\n", cas_c++, sol);
 }
 return 0;
}

//State: HDU4280居然用了2700ms+,牛逼模版
/*
   This Problem beat me completely.
   Beat my template completely.
   Beat my funtion comletely.
   Waste my time comletely.

   It's a naked maximum-stream problem.
   The main point is your template.

   It make me realize that my SAP template is a sh*t!

   ....To make my SAP faster, I have done three kinds of optimization.
   1. Record the adjacency node which has minimum distance;
   2. Initailize the distance by using BFS;
   3. As I got a Stack-Overflow, I simulate the DFS by using stack in STL;

   Then I got AC in 2s+.

   Of course, the problem is also correspond to the Minimum-Cut in Dual-Graph.
   Hence, Dijkstra with minimum heap is optimal algorithm.
   */
//Header
//#include 
//#include 
//#include 
//#include 
//#include 
//#include 
//#include 

//邻接表——sha
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define VM 10001
#define EM 500100

#define pi 3.1415926535897932
#define abs(x) ((x)>0?(x):-(x))
#define sqr(x) ((x)*(x))
#define fill(m,v) memset(m,v,sizeof(m))
#define SS(x) scanf("%d",&x)

#define inf 0x7fffffff
#define hinf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rall(v) v.rbegin(),v.rend()
#define sz(v) ((int)v.size())
#define y0 stupid_cmath
#define y1 very_stupid_cmath
#define ll __int64
#define ull unsigned __int64
#define pb push_back
#define mp make_pair
#define rep(i,m) for(int i=0;i<(int)(m);i++)
#define rep2(i,n,m) for(int i=n;i<(int)(m);i++)
#define FOR(i,a,b)  for(int i = (a); i < (b); i++)
#define FF(i,a)   for(int i = 0; i < (a); i++ )
#define FFD(i,a)  for(int i = (a)-1; i >= 0; i--)
#define CC(m,what)  memset(m,what,sizeof(m))
#define SZ(a)   ((int)a.size())
#define PP(n,m,a)  puts("---");FF(i,n){FF(j,m)cout << a[i][j] << ' ';puts("");}

#define read   freopen("in.txt","r",stdin)
#define write   freopen("out.txt","w",stdout)
int dx[] = {-1, 0, 1, 0};//up Right down Left
int dy[] = {0,  1, 0, -1};
//#define For(it,c) for(__typeof(c.begin()) it=c.begin();it!=c.end();++it)

using namespace std;
#define M 40010
template inline void checkmin(T &a,T b) {if(a == -1 || a > b)a = b;}
template inline void checkmax(T &a,T b) {if(a < b) a = b;}

int gap[M],dis[M],pre[M],cur[M];
int NE,NV;
int head[M];
struct Node{
 int c,pos,next;
}E[999999];
int sap(int s,int t) {
 memset(dis,0,sizeof(int)*(NV+1));
 memset(gap,0,sizeof(int)*(NV+1));
 FF(i,NV) cur[i] = head[i];
 int u = pre[s] = s,maxflow = 0,aug = -1;
 gap[0] = NV;
 while(dis[s] < NV) {
loop:  for(int &i = cur[u]; i != -1; i = E[i].next) {
   int v = E[i].pos;
   if(E[i].c && dis[u] == dis[v] + 1) {
    checkmin(aug,E[i].c);
    pre[v] = u;
    u = v;
    if(v == t) {
     maxflow += aug;
     for(u = pre[u];v != s;v = u,u = pre[u]) {
      E[cur[u]].c -= aug;
      E[cur[u]^1].c += aug;
     }
     aug = -1;
    }
    goto loop;
   }
  }
  int mindis = NV;
  for(int i = head[u]; i != -1 ; i = E[i].next) {
   int v = E[i].pos;
   if(E[i].c && mindis > dis[v]) {
    cur[u] = i;
    mindis = dis[v];
   }
  }
  if( (--gap[dis[u]]) == 0)    break;
  gap[ dis[u] = mindis+1 ] ++;
  u = pre[u];
 }
 return maxflow;
}
void Insert(int u,int v,int c,int cc = 0) {
 E[NE].c = c; E[NE].pos = v;
 E[NE].next = head[u]; head[u] = NE++;
 E[NE].c = cc; E[NE].pos = u;
 E[NE].next = head[v]; head[v] = NE++;
}

int main() {
 FF(i,NV) head[i] = -1;
 NE = 0;
}