hdu 4280 最大流sap
模板套起来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
13 int tol;
14 int head;
15 int gap,dep,cur;
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.to = v; edge.cap = w; edge.flow = 0;
24 edge.next = head; head = tol++;
25 edge.to = u; edge.cap = rw; edge.flow = 0;
26 edge.next = head; head = tol++;
27 }
28 int Q;
29 void BFS(int start,int end)
30 {
31 memset(dep,-1,sizeof(dep));
32 memset(gap,0,sizeof(gap));
33 gap = 1;
34 int front = 0, rear = 0;
35 dep = 0;
36 Q = end;
37 while(front != rear)
38 {
39 int u = Q;
40 for(int i = head; i != -1; i = edge.next)
41 {
42 int v = edge.to;
43 if(dep != -1)continue;
44 Q = v;
45 dep = dep + 1;
46 gap]++;
47 }
48 }
49 }
50 int S;
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 < 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].cap - edge].flow)
66 {
67 Min = edge].cap - edge].flow;
68 inser = i;
69 }
70 for(int i = 0;i < top;i++)
71 {
72 edge].flow += Min;
73 edge^1].flow -= Min;
74 }
75 ans += Min;
76 top = inser;
77 u = edge^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+1 == dep)
86 {
87 flag = true;
88 cur = i;
89 break;
90 }
91 }
92 if(flag)
93 {
94 S = 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.to] < Min)
101 {
102 Min = dep.to];
103 cur = i;
104 }
105 gap]--;
106 if(!gap])return ans;
107 dep = Min + 1;
108 gap]++;
109 if(u != start)u = edge^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 }
页:
[1]