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

/*
最大流模板
isap復雜度(v^2*e)
*/
/*
*State: HDU4280 3609MS 8860K 3571 B C++
*題目大意：
*  有N個島嶼 M條無向路 每個路有一最大允許的客流量，求從最西的那個島嶼最多能運
*  用多少乘客到最東的那個島嶼。
*解題思路：
*  很單純的網絡流，重點是卡時間 模板的高效性很重要啊該模板詳解
*  參見這里  模板題就不注釋了
*解題感想：
*  10000ms的時間里，大多數最大流算法都掛掉了，就這個堅持下來了，用了3000ms左右。
*/

#include <stdio.h>
#include <iostream>
#include <string.h>
#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 <iostream>
#include <cstring>
#include <cstdio>

#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 <cstdio>
//#include <cstdlib>
//#include <iostream>
//#include <cstring>
//#include <string>
//#include <vector>
//#include <map>
//#include <algorithm>
//#include <cctype>
//#include <queue>
//#include <stack>
//#include <cmath>
//using namespace std;
////Macro
////STL-Alias
//#define UN(c, a) unique(c, a)
//#define MS(c, a) memset(c, a, sizeof c)
//#define FLC(c, a ,b) fill(c, c + a, b)
//#define LOS(c, a, b) lower_bound(c, a, b)
//#define UPS(c, a, b) upper_bound(c, a, b)
////Syntax-Alias
//#define Rep(c, a, b) for (int c = (a); c < (b); c++)
//#define Nre(c, a, b) for (int c = (a); c > (b); c--)
////DEBUG
//#define FK puts("Fu*k here!")
//#define PA(s, c, a, b, p, f){\
// printf(s);\
// Rep(c, a, b) printf(p, (f));\
// puts("");}
////Constant
//#define INFL (0x7fffffffffffffffLL)
//#define INFI (0x7fffffff)
//#define MOD ()
//#define MAXN (100005)
////Type-Alias
//typedef long long LL;
//typedef long double LD;
//typedef int AI[MAXN];
//typedef bool AB[MAXN];
//typedef double AD[MAXN];
//typedef LL ALL[MAXN];
//typedef LD ALD[MAXN];
//
//
////FSG
//struct Edge
//{
//    int v, w, next;
//};
//vector<Edge> E;
//AI L;
//void G_ini()
//{
// E.clear();
// MS(L, -1);
//}
//void AE(int u, int v, int w)
//{
// Edge te = {v, w, L[u]};
// L[u] = E.size();
// E.push_back(te);
//}
//#define Ere(c, a, L) for (int c = L[a]; c != -1; c = E[c].next)
//
//
////ISAP
//int ISAP(int src, int snk, int V)
//{
// static AI dis, gap, _L, se;
// int u = src, mxf = 0, te = 0;
// memcpy(_L, L, sizeof L);
// MS(dis, -1); MS(gap, 0);
// gap[dis[snk] = 0] = 1;
// queue<int> Q;
// Q.push(snk);
// while (!Q.empty())
// {
//  int u = Q.front(); Q.pop();
//  Ere(i, u, L) if (E[i].w && dis[E[i].v] < 0)
//  {
//   gap[dis[E[i].v] = dis[u] + 1]++;
//   Q.push(E[i].v);
//  }
// }
// while (dis[src] < V)
// {
//  int _i = -1;
//  Ere(i, u, _L) if (E[i].w && dis[u] == dis[E[i].v] + 1)
//  {
//   _i = i;
//   break;
//  }
//  if (_i != -1)
//  {
//   _L[u] = _i;
//   u = E[se[te++] = _i].v;
//  }
//  else
//  {
//   int md = INFI;
//   _i = -1;
//   Ere(i, u, L) if (E[i].w && dis[E[i].v] < md)
//   {
//    md = dis[E[i].v];
//    _L[u] = i;
//   }
//   if (!--gap[dis[u]]) break;
//   gap[dis[u] = md + 1]++;
//   if (u != src) u = E[se[te-- - 1] ^ 1].v;
//  }
//  if (u == snk)
//  {
//   int _i = 0, mf = INFI;
//   Rep(i, 0, te) if (E[se[i]].w < mf)
//   {
//    mf = E[se[i]].w;
//    _i = i;
//   }
//   Rep(i, 0, te)
//   {
//    E[se[i]].w -= mf;
//    E[se[i] ^ 1].w += mf;
//   }
//   mxf += mf;
//   te = _i;
//   u = E[se[_i] ^ 1].v;
//  }
// }
// return mxf;
//}
//
//
//struct Isl
//{
// int x, y;
// void inp()
// {
//  scanf("%d%d", &x, &y);
// }
//} I[MAXN];
//int n, m;
//
//
//int main()
//{
// int T;
// scanf("%d", &T);
// while (T--)
// {
//  //Initialize
//  scanf("%d%d", &n, &m);
//  I[0].inp();
//  int src = 0, snk = 0;
//  Rep(i, 1, n)
//  {
//   I[i].inp();
//   if (I[i].x < I[src].x) src = i;
//   if (I[i].x > I[snk].x) snk = i;
//  }
//  G_ini();
//  while (m--)
//  {
//   int u, v, w;
//   scanf("%d%d%d", &u, &v, &w);
//   u--;
//   v--;
//   AE(u, v, w);
//   AE(v, u, w);
//  }
//  //Solve
//  printf("%d\n", ISAP(src, snk, n));
// }
// return 0;
//}
//
//
//
//
//
//
////isap深搜版，以HDU4280長春網絡賽的題目為例，不過那題10000ms都TLE
////不知道dfs版有什么長處，據說dfs版比dinic要快。
//#include <iostream>
//using namespace std;
//
//typedef  struct {int v,next,val;} edge;
//const int MAXN=100005;
//const int MAXM=500010;
//const int inf = 0x3f3f3f3f;
//edge e[MAXM];
//int p[MAXN],eid;
// 
//inline void init(){memset(p,-1,sizeof(p));eid=0;}
// 
////有向
//inline void insert1(int from,int to,int val)
//{
//    e[eid].v=to;
//    e[eid].val=val;
//    e[eid].next=p[from];
//    p[from]=eid++;
// 
//    swap(from,to);
// 
//    e[eid].v=to;
//    e[eid].val=0;
//    e[eid].next=p[from];
//    p[from]=eid++;
//}
// 
////無向
//inline void insert2(int from,int to,int val)
//{
//    e[eid].v=to;
//    e[eid].val=val;
//    e[eid].next=p[from];
//    p[from]=eid++;
// 
//    swap(from,to);
// 
//    e[eid].v=to;
//    e[eid].val=val;
//    e[eid].next=p[from];
//    p[from]=eid++;
//}
// 
//int n,m;//n為點數 m為邊數
//int h[MAXN];
//int gap[MAXN];
// 
//int source,sink;
//inline int dfs(int pos,int cost)
//{
//    if (pos==sink)
//    {
//        return cost;
//    }
// 
//    int j,minh=n-1,lv=cost,d;
// 
//    for (j=p[pos];j!=-1;j=e[j].next)
//    {
//        int v=e[j].v,val=e[j].val;
//        if(val>0)
//        {
//            if (h[v]+1==h[pos])
//            {
//                if (lv<e[j].val) d=lv;
//                else d=e[j].val;
// 
//                d=dfs(v,d);
//                e[j].val-=d;
//                e[j^1].val+=d;
//                lv-=d;
//                if (h[source]>=n) return cost-lv;
//                if (lv==0) break;
//            }
// 
//            if (h[v]<minh)    minh=h[v];
//        }
//    }
// 
//    if (lv==cost)
//    {
//        --gap[h[pos]];
//        if (gap[h[pos]]==0) h[source]=n;
//        h[pos]=minh+1;
//        ++gap[h[pos]];
//    }
// 
//    return cost-lv;
// 
//}
// 
//int sap(int st,int ed)
//{
// 
//    source=st;
//    sink=ed;
//    int ret=0;
//    memset(gap,0,sizeof(gap));
//    memset(h,0,sizeof(h));
// 
//    gap[st]=n;
// 
//    while (h[st]<n)
//    {
//        ret+=dfs(st,INT_MAX);
//    }
// 
//    return ret;
//}
//
//
//int main()
//{
//#ifndef ONLINE_JUDGE
// freopen("in.txt", "r", stdin);
//#endif
//    int T;
//    scanf("%d", &T);
//    while (T--)
//    {
//        scanf("%d%d", &n, &m);
//        int x, y;
//        int Min = inf, Max = -inf;
//  int src, des;
//        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);
//   insert2(u, v, c);
//        }
//       
//        printf("%d\n", sap(src,des));
//    }
//    return 0;
//}

//鄰接表——sha
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <functional>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <utility>
#include <stack>
#include <queue>
#include <deque>
#include <iomanip>

#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<class T> inline void checkmin(T &a,T b) {if(a == -1 || a > b)a = b;}
template<class T> 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;
}