题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4280

题意：给你n个岛屿的坐标，让你求从最西边到最东边的最大流

（题目保证只有一个点在最西边，只有一个点在最东边）

这个题比较卡时间

普通 dinic（） 9375ms

kuangbin模板  4992ms

ISAP+bfs初始化+栈优化  3572ms

 

#include <algorithm>
#include <vector>
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX = (1ll << 31) - 1;
const int mavn = 1e5+5;
const int maxn = 1e5+5;
#define ll long long
struct Edge{
    int to;
    int cap;
    int rev;
    Edge(){}
    Edge(int to,int d,int c):to(to),cap(d),rev(c){}
} ;
vector<Edge> v[mavn];

int n, m, s, t;
struct node {
    int x,y,id;
    bool operator < (const node& aa) const {
        return x < aa.x;
    }
}pos[mavn];
void addEdge(int from, int to, int cap){
    v[from].push_back(Edge(to, cap,v[to].size()));
    v[to].push_back(Edge(from, cap,v[from].size()-1));
}
int d[mavn],cnt, cur[mavn];
int DFS(int u, int flow){
    if (u == t || !flow) return flow;
    int ans = 0, tmp_flow;
    for (int& i = cur[u]; i < v[u].size(); i++){
        int to = v[u][i].to;
        if (d[to] == d[u] + 1 && v[u][i].cap > 0){
            tmp_flow = DFS(to, min(flow, v[u][i].cap));
            if(tmp_flow > 0) {
                flow -= tmp_flow;
                v[u][i].cap -= tmp_flow;
                ans += tmp_flow;
                v[to][v[u][i].rev].cap += tmp_flow;
                if (!flow)
                    break;
            }
        }
    }
    if (!ans) d[u] = -1;
    return ans;
}
bool BFS(){
    for(int i=1;i<=n;i++) d[i] = -1;
    queue<int> que;
    que.push(s);
    d[s] = 0;
    int u, _new;
    while (!que.empty()){
        u = que.front();
        que.pop();
        for (int i = 0; i < v[u].size(); i++){
            _new = v[u][i].to;
            if (d[_new] == -1 && v[u][i].cap > 0){
                d[_new] = d[u] + 1;
                que.push(_new);
            }
        }
    }
    return (d[t] != -1);
}

int  dinic(){
    int max_flow = 0;
    while (BFS()){
        for(int i=1;i<=n;i++) cur[i] = 0;
        int tt;
        while((tt = DFS(s,MAX)) > 0) max_flow += tt;
    }
    return max_flow;
}

int T, x, y,minn,maxx;

int main(){
    scanf("%d",&T);
    while(T--) {
        minn = 99999999,maxx = -99999999;
        scanf("%d%d",&n,&m);
        for(int i=0;i<=n;i++) v[i].clear();
        for(int i=1;i<=n;i++) {
            scanf("%d%d",&x,&y);
            if(minn > x) {
                minn = x;
                s = i;
            }
            if(maxx < x) {
                maxx = x;
                t = i;
            }
        }
        for(int i=1 ; i<=m ; ++i){
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
    	    addEdge(a,b,c);
        }
        printf("%d\n",dinic());
    }
    return 0;
}