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

  1 #pragma comment(linker, "/STACK:1024000000,1024000000")
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <cmath>
  5 #include <string>
  6 #include <cstring>
  7 #include <algorithm>
  8 #include <limits>
  9 #include <vector>
 10 #include <stack>
 11 #include <queue>
 12 #include <set>
 13 #include <map>
 14 #define lowbit(x) ( x&(-x) )
 15 #define pi 3.141592653589793
 16 #define e 2.718281828459045
 17 #define INF 0x3f3f3f3f
 18 #define HalF (l + r)>>1
 19 #define lsn rt<<1
 20 #define rsn rt<<1|1
 21 #define Lson lsn, l, mid
 22 #define Rson rsn, mid+1, r
 23 #define QL Lson, ql, qr
 24 #define QR Rson, ql, qr
 25 #define myself rt, l, r
 26 using namespace std;
 27 typedef unsigned long long ull;
 28 typedef long long ll;
 29 const int maxN = 1e5 + 7;
 30 int N, M, S, T, head[maxN], cnt, cur[maxN];
 31 struct Eddge
 32 {
 33     int nex, to, flow;
 34     Eddge(int a=-1, int b=0, int c=0):nex(a), to(b), flow(c) {}
 35 }edge[maxN<<1];
 36 inline void addEddge(int u, int v, int flow)
 37 {
 38     edge[cnt] = Eddge(head[u], v, flow);
 39     head[u] = cnt++;
 40 }
 41 inline void _add(int u, int v, int flow) { addEddge(u, v, flow); addEddge(v, u, 0); }
 42 int deep[maxN];
 43 int Q[maxN<<1], top, tail;
 44 bool bfs()
 45 {
 46     for(int i=1; i<=N; i++) deep[i] = 0;
 47     deep[S] = 1;
 48     top = tail = 0;
 49     Q[++top] = S;
 50     while(tail < top)
 51     {
 52         int u = Q[++tail];
 53         if(u == T) break;
 54         for(int i=head[u], v, f; ~i; i=edge[i].nex)
 55         {
 56             v = edge[i].to; f = edge[i].flow;
 57             if(f > 0 && !deep[v])
 58             {
 59                 deep[v] = deep[u] + 1;
 60                 Q[++top] = v;
 61             }
 62         }
 63     }
 64     return deep[T];
 65 }
 66 int dfs(int u, int dist)
 67 {
 68     if(u == T) return dist;
 69     for(int &i=cur[u], v, f; ~i; i=edge[i].nex)
 70     {
 71         v = edge[i].to; f = edge[i].flow;
 72         if(deep[v] == deep[u] + 1 && f > 0)
 73         {
 74             int di = dfs(v, min(dist, f));
 75             if(di)
 76             {
 77                 edge[i].flow -= di;
 78                 edge[i^1].flow += di;
 79                 return di;
 80             }
 81         }
 82     }
 83     return 0;
 84 }
 85 int Dinic()
 86 {
 87     int ans = 0, tmp;
 88     while(bfs())
 89     {
 90         for(int i=1; i<=N; i++) cur[i] = head[i];
 91         while((tmp = dfs(S, INF))) ans += tmp;
 92     }
 93     return ans;
 94 }
 95 inline void init()
 96 {
 97     cnt = 0;
 98     for(int i=1; i<=N; i++) head[i] = -1;
 99 }
100 int main()
101 {
102     int Cas;  scanf("%d", &Cas);
103     while(Cas--)
104     {
105         scanf("%d%d", &N, &M);
106         init();
107         int minn = INF, maxx = -INF;
108         for(int i=1, x, y; i<=N; i++)
109         {
110             scanf("%d%d", &x, &y);
111             if(x < minn)
112             {
113                 minn = x;
114                 S = i;
115             }
116             if(x > maxx)
117             {
118                 maxx = x;
119                 T = i;
120             }
121         }
122         for(int i=1, u, v, w; i<=M; i++)
123         {
124             scanf("%d%d%d", &u, &v, &w);
125             //_add(u, v, w);
126             //_add(v, u, w);
127             addEddge(u, v, w);
128             addEddge(v, u, w);
129         }
130         printf("%dn", Dinic());
131     }
132     return 0;
133 }