Island Transport 【HDU - 4280】【最大流Dinic】

题目链接

可以说是真的把时间卡爆了，不断的修改了好多次之后才A了，一直T一直T，哭了……

可以说是很练时间优化了，不断的改，不断的提交，最后竟然是改了Dinic中的BFS()中，我们一旦搜索到了T之后就是直接break掉，就可以过了。还有一个优化就是在Dinic上面需要加当前弧优化操作才可以，另外不知道改出来的手动队列到最后有没有派上用处。

 #pragma comment(linker, "/STACK:1024000000,1024000000")

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <string>

 #include <cstring>

 #include <algorithm>

 #include <limits>

 #include <vector>

 #include <stack>

 #include <queue>

 #include <set>

 #include <map>

 #define lowbit(x) ( x&(-x) )

 #define pi 3.141592653589793

 #define e 2.718281828459045

 #define INF 0x3f3f3f3f

 #define HalF (l + r)>>1

 #define lsn rt<<1

 #define rsn rt<<1|1

 #define Lson lsn, l, mid

 #define Rson rsn, mid+1, r

 #define QL Lson, ql, qr

 #define QR Rson, ql, qr

 #define myself rt, l, r

 using namespace std;

 typedef unsigned long long ull;

 typedef long long ll;

 const int maxN = 1e5 + ;

 int N, M, S, T, head[maxN], cnt, cur[maxN];

 struct Eddge

 {

     int nex, to, flow;

     Eddge(int a=-, int b=, int c=):nex(a), to(b), flow(c) {}

 }edge[maxN<<];

 inline void addEddge(int u, int v, int flow)

 {

     edge[cnt] = Eddge(head[u], v, flow);

     head[u] = cnt++;

 }

 inline void _add(int u, int v, int flow) { addEddge(u, v, flow); addEddge(v, u, ); }

 int deep[maxN];

 int Q[maxN<<], top, tail;

 bool bfs()

 {

     for(int i=; i<=N; i++) deep[i] = ;

     deep[S] = ;

     top = tail = ;

     Q[++top] = S;

     while(tail < top)

     {

         int u = Q[++tail];

         if(u == T) break;

         for(int i=head[u], v, f; ~i; i=edge[i].nex)

         {

             v = edge[i].to; f = edge[i].flow;

             if(f >  && !deep[v])

             {

                 deep[v] = deep[u] + ;

                 Q[++top] = v;

             }

         }

     }

     return deep[T];

 }

 int dfs(int u, int dist)

 {

     if(u == T) return dist;

     for(int &i=cur[u], v, f; ~i; i=edge[i].nex)

     {

         v = edge[i].to; f = edge[i].flow;

         if(deep[v] == deep[u] +  && f > )

         {

             int di = dfs(v, min(dist, f));

             if(di)

             {

                 edge[i].flow -= di;

                 edge[i^].flow += di;

                 return di;

             }

         }

     }

     return ;

 }

 int Dinic()

 {

     int ans = , tmp;

     while(bfs())

     {

         for(int i=; i<=N; i++) cur[i] = head[i];

         while((tmp = dfs(S, INF))) ans += tmp;

     }

     return ans;

 }

 inline void init()

 {

     cnt = ;

     for(int i=; i<=N; i++) head[i] = -;

 }

 int main()

 {

     int Cas;  scanf("%d", &Cas);

     while(Cas--)

     {

         scanf("%d%d", &N, &M);

         init();

         int minn = INF, maxx = -INF;

         for(int i=, x, y; i<=N; i++)

         {

             scanf("%d%d", &x, &y);

             if(x < minn)

             {

                 minn = x;

                 S = i;

             }

             if(x > maxx)

             {

                 maxx = x;

                 T = i;

             }

         }

         for(int i=, u, v, w; i<=M; i++)

         {

             scanf("%d%d%d", &u, &v, &w);

             //_add(u, v, w);

             //_add(v, u, w);

             addEddge(u, v, w);

             addEddge(v, u, w);

         }

         printf("%d\n", Dinic());

     }

     return ;

 }