hdu 4280 最大流sap

zcl_ccc

　　模板套起来

1　　
5 7　　//5个结点，7个边
3 3　　//坐标
3 0　　
3 1
0 0
4 5
1 3 3　　//相连的结点和流
2 3 4
2 4 3
1 5 6
4 5 3
1 4 4
3 4 2
9


  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cstring>
  4 using namespace std;
  5 const int MAXN = 100010;//点数的最大值
  6 const int MAXM = 400010;//边数的最大值
  7 const int INF = 0x3f3f3f3f;
  8 int n;
  9 struct Edge
10 {
11     int to,next,cap,flow;
12 }edge[MAXM];//注意是MAXM
13 int tol;
14 int head[MAXN];
15 int gap[MAXN],dep[MAXN],cur[MAXN];
16 void init()
17 {
18     tol = 0;
19     memset(head,-1,sizeof(head));
20 }
21 void addedge(int u,int v,int w,int rw = 0)
22 {
23     edge[tol].to = v; edge[tol].cap = w; edge[tol].flow = 0;
24     edge[tol].next = head; head = tol++;
25     edge[tol].to = u; edge[tol].cap = rw; edge[tol].flow = 0;
26     edge[tol].next = head[v]; head[v] = tol++;
27 }
28 int Q[MAXN];
29 void BFS(int start,int end)
30 {
31     memset(dep,-1,sizeof(dep));
32     memset(gap,0,sizeof(gap));
33     gap[0] = 1;
34     int front = 0, rear = 0;
35     dep[end] = 0;
36     Q[rear++] = end;
37     while(front != rear)
38     {
39         int u = Q[front++];
40         for(int i = head; i != -1; i = edge.next)
41         {
42             int v = edge.to;
43             if(dep[v] != -1)continue;
44             Q[rear++] = v;
45             dep[v] = dep + 1;
46             gap[dep[v]]++;
47         }
48     }
49 }
50 int S[MAXN];
51 int SAP(int start,int end,int N)
52 {
53     BFS(start,end);
54     memcpy(cur,head,sizeof(head));
55     int top = 0;
56     int u = start;
57     int ans = 0;
58     while(dep[start] < N)
59     {
60         if(u == end)
61         {
62             int Min = INF;
63             int inser;
64             for(int i = 0;i < top;i++)
65             if(Min > edge[S].cap - edge[S].flow)
66             {
67                 Min = edge[S].cap - edge[S].flow;
68                 inser = i;
69             }
70             for(int i = 0;i < top;i++)
71             {
72                 edge[S].flow += Min;
73                 edge[S^1].flow -= Min;
74             }
75             ans += Min;
76             top = inser;
77             u = edge[S[top]^1].to;
78             continue;
79         }
80         bool flag = false;
81         int v;
82         for(int i = cur; i != -1; i = edge.next)
83         {
84             v = edge.to;
85             if(edge.cap - edge.flow && dep[v]+1 == dep)
86             {
87                 flag = true;
88                 cur = i;
89                 break;
90             }
91         }
92         if(flag)
93         {
94             S[top++] = cur;
95             u = v;
96             continue;
97         }
98         int Min = N;
99         for(int i = head; i != -1; i = edge.next)
100         if(edge.cap - edge.flow && dep[edge.to] < Min)
101         {
102             Min = dep[edge.to];
103             cur = i;
104         }
105         gap[dep]--;
106         if(!gap[dep])return ans;
107         dep = Min + 1;
108         gap[dep]++;
109         if(u != start)u = edge[S[--top]^1].to;
110         }
111     return ans;
112 }
113 int main()
114 {
115     #ifndef ONLINE_JUDGE
116     freopen("1.in","r",stdin);
117     #endif
118     int start,end;
119     int m;
120     int u,v,z;
121     int T;
122     scanf("%d",&T);
123     while(T--)
124     {
125         init();
126         scanf("%d%d",&n,&m);
127         int minx=10000000;
128         int maxx=-10000000;
129         int x,y;
130         for(int i=1;i<=n;i++)
131         {
132             scanf("%d%d",&x,&y);
133             if(minx>x)
134             {
135                 minx=x;
136                 start=i;
137             }
138             if(maxx<x)
139             {
140                 maxx=x;
141                 end=i;
142             }
143         }
144         while(m--)
145         {
146             scanf("%d%d%d",&u,&v,&z);
147             addedge(u,v,z);
148             addedge(v,u,z);
149         }
150         int ans=SAP(start,end,n);
151         printf("%d\n",ans);
152     }
153     return 0;
154 }