当前位置：网站首页>POJ1273 Drainage Ditches【最大流】【SAP】

POJ1273 Drainage Ditches【最大流】【SAP】

2022-07-27 12:34:00 【51CTO】
题目链接：
http://poj.org/problem?id=1273
题目大意：
农民John的田里有M个池塘和N条水沟用来排水，池塘编号为1~M，1号池塘是所有水沟的源点，
M号池塘是水沟的汇点。给你N条水沟所连接的池塘和所能流过的水量，求整个水沟从源点到汇点
最多能流多少水。
思路：
很明显的求网络流最大流问题。用链式前向星(邻接表)来存储网络，这样就不用考虑重边问题了。这
里的重边其实就是平行边。用SAP算法+GAP优化来求最大流就可以了。
AC代码：
       
       #include<iostream>
       
       #include<algorithm>
       
       #include<cstdio>
       
       #include<cstring>
       
       #include<queue>
       
       using 
       
       namespace 
       
       std;
       
       const 
       
       int 
       
       MAXN 
       
       = 
       
       220;
       
       const 
       
       int 
       
       MAXM 
       
       = 
       
       MAXN
       
       *
       
       MAXN;
       
       const 
       
       int 
       
       INF 
       
       = 
       
       0xffffff0;
       
       struct 
       
       EdgeNode
       
{
       
       int 
       
       to;
       
       int 
       
       w;
       
       int 
       
       next;
       
}
       
       Edges[
       
       MAXM];
       
       int 
       
       Head[
       
       MAXN],
       
       id;
       
       void 
       
       AddEdges(
       
       int 
       
       u,
       
       int 
       
       v,
       
       int 
       
       w)
       
{
       
       Edges[
       
       id].
       
       to 
       
       = 
       
       v;
       
       Edges[
       
       id].
       
       w 
       
       = 
       
       w;
       
       Edges[
       
       id].
       
       next 
       
       = 
       
       Head[
       
       u];
       
       Head[
       
       u] 
       
       = 
       
       id
       
       ++;
       
       Edges[
       
       id].
       
       to 
       
       = 
       
       u;
       
       Edges[
       
       id].
       
       w 
       
       = 
       
       0;
       
       Edges[
       
       id].
       
       next 
       
       = 
       
       Head[
       
       v];
       
       Head[
       
       v] 
       
       = 
       
       id
       
       ++;
       
}
       
       int 
       
       Numh[
       
       MAXN],
       
       h[
       
       MAXN],
       
       curedges[
       
       MAXN],
       
       pre[
       
       MAXN];
       
       void 
       
       BFS(
       
       int 
       
       end,
       
       int 
       
       N)
       
{
       
       memset(
       
       Numh,
       
       0,
       
       sizeof(
       
       Numh));
       
       for(
       
       int 
       
       i 
       
       = 
       
       1; 
       
       i 
       
       <= 
       
       N; 
       
       ++
       
       i)
       
       Numh[
       
       h[
       
       i]
       
       =
       
       N]
       
       ++;
       
       h[
       
       end] 
       
       = 
       
       0;
       
       Numh[
       
       N]
       
       --;
       
       Numh[
       
       0]
       
       ++;
       
       queue
       
       <
       
       int
       
       > 
       
       Q;
       
       Q.
       
       push(
       
       end);
       
       while(
       
       !
       
       Q.
       
       empty())
       
    {
       
       int 
       
       v 
       
       = 
       
       Q.
       
       front();
       
       Q.
       
       pop();
       
       int 
       
       i 
       
       = 
       
       Head[
       
       v];
       
       while(
       
       i 
       
       != 
       
       -
       
       1)
       
        {
       
       int 
       
       u 
       
       = 
       
       Edges[
       
       i].
       
       to;
       
       if(
       
       h[
       
       u] 
       
       < 
       
       N)
       
            {
       
       i 
       
       = 
       
       Edges[
       
       i].
       
       next;
       
       continue;
       
            }
       
       h[
       
       u] 
       
       = 
       
       h[
       
       v] 
       
       + 
       
       1;
       
       Numh[
       
       N]
       
       --;
       
       Numh[
       
       h[
       
       u]]
       
       ++;
       
       Q.
       
       push(
       
       u);
       
       i 
       
       = 
       
       Edges[
       
       i].
       
       next;
       
        }
       
    }
       
}
       
       int 
       
       SAP(
       
       int 
       
       start,
       
       int 
       
       end,
       
       int 
       
       N)
       
{
       
       int 
       
       Curflow,
       
       FlowAns 
       
       = 
       
       0,
       
       temp,
       
       neck;
       
       memset(
       
       h,
       
       0,
       
       sizeof(
       
       h));
       
       memset(
       
       pre,
       
       -
       
       1,
       
       sizeof(
       
       pre));
       
       for(
       
       int 
       
       i 
       
       = 
       
       1; 
       
       i 
       
       <= 
       
       N; 
       
       ++
       
       i)
       
       curedges[
       
       i] 
       
       = 
       
       Head[
       
       i];
       
       BFS(
       
       end,
       
       N);
       
       int 
       
       u 
       
       = 
       
       start;
       
       while(
       
       h[
       
       start] 
       
       < 
       
       N)
       
    {
       
       if(
       
       u 
       
       == 
       
       end)
       
        {
       
       Curflow 
       
       = 
       
       INF;
       
       for(
       
       int 
       
       i 
       
       = 
       
       start; 
       
       i 
       
       != 
       
       end; 
       
       i 
       
       = 
       
       Edges[
       
       curedges[
       
       i]].
       
       to)
       
            {
       
       if(
       
       Curflow 
       
       > 
       
       Edges[
       
       curedges[
       
       i]].
       
       w)
       
                {
       
       neck 
       
       = 
       
       i;
       
       Curflow 
       
       = 
       
       Edges[
       
       curedges[
       
       i]].
       
       w;
       
                }
       
            }
       
       for(
       
       int 
       
       i 
       
       = 
       
       start; 
       
       i 
       
       != 
       
       end; 
       
       i 
       
       = 
       
       Edges[
       
       curedges[
       
       i]].
       
       to)
       
            {
       
       temp 
       
       = 
       
       curedges[
       
       i];
       
       Edges[
       
       temp].
       
       w 
       
       -= 
       
       Curflow;
       
       Edges[
       
       temp
       
       ^1].
       
       w 
       
       += 
       
       Curflow;
       
            }
       
       FlowAns 
       
       += 
       
       Curflow;
       
       u 
       
       = 
       
       neck;
       
        }
       
       int 
       
       i;
       
       for(
       
       i 
       
       = 
       
       curedges[
       
       u]; 
       
       i 
       
       != 
       
       -
       
       1; 
       
       i 
       
       = 
       
       Edges[
       
       i].
       
       next)
       
       if(
       
       Edges[
       
       i].
       
       w 
       
       && 
       
       h[
       
       u]
       
       ==
       
       h[
       
       Edges[
       
       i].
       
       to]
       
       +
       
       1)
       
       break;
       
       if(
       
       i 
       
       != 
       
       -
       
       1)
       
        {
       
       curedges[
       
       u] 
       
       = 
       
       i;
       
       pre[
       
       Edges[
       
       i].
       
       to] 
       
       = 
       
       u;
       
       u 
       
       = 
       
       Edges[
       
       i].
       
       to;
       
        }
       
       else
       
        {
       
       if(
       
       0 
       
       == 
       
       --
       
       Numh[
       
       h[
       
       u]])
       
       break;
       
       curedges[
       
       u] 
       
       = 
       
       Head[
       
       u];
       
       for(
       
       temp 
       
       = 
       
       N,
       
       i 
       
       = 
       
       Head[
       
       u]; 
       
       i 
       
       != 
       
       -
       
       1; 
       
       i 
       
       = 
       
       Edges[
       
       i].
       
       next)
       
       if(
       
       Edges[
       
       i].
       
       w)
       
       temp 
       
       = 
       
       min(
       
       temp,
       
       h[
       
       Edges[
       
       i].
       
       to]);
       
       h[
       
       u] 
       
       = 
       
       temp 
       
       + 
       
       1;
       
       ++
       
       Numh[
       
       h[
       
       u]];
       
       if(
       
       u 
       
       != 
       
       start)
       
       u 
       
       = 
       
       pre[
       
       u];
       
        }
       
    }
       
       return 
       
       FlowAns;
       
}
       
       int 
       
       main()
       
{
       
       int 
       
       N,
       
       M,
       
       u,
       
       v,
       
       w;
       
       while(
       
       ~scanf(
       
       "%d%d",
       
       &
       
       N,
       
       &
       
       M))
       
    {
       
       memset(
       
       Head,
       
       -
       
       1,
       
       sizeof(
       
       Head));
       
       id 
       
       = 
       
       0;
       
       for(
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       N; 
       
       ++
       
       i)
       
        {
       
       scanf(
       
       "%d%d%d",
       
       &
       
       u,
       
       &
       
       v,
       
       &
       
       w);
       
       AddEdges(
       
       u,
       
       v,
       
       w);
       
        }
       
       printf(
       
       "%d\n",
       
       SAP(
       
       1,
       
       M,
       
       M));
       
    }
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
原网站
版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/ITCharge/5518554
当前位置：网站首页>POJ1273 Drainage Ditches【最大流】【SAP】

POJ1273 Drainage Ditches【最大流】【SAP】

边栏推荐

猜你喜欢

随机推荐
