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];//注意是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[u]; head[u] = 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[u]; i != -1; i = edge[i].next)
 41         {
 42             int v = edge[i].to;
 43             if(dep[v] != -1)continue;
 44             Q[rear++] = v;
 45             dep[v] = dep[u] + 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[i]].cap - edge[S[i]].flow)
 66             {
 67                 Min = edge[S[i]].cap - edge[S[i]].flow;
 68                 inser = i;
 69             }
 70             for(int i = 0;i < top;i++)
 71             {
 72                 edge[S[i]].flow += Min;
 73                 edge[S[i]^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[u]; i != -1; i = edge[i].next)
 83         {
 84             v = edge[i].to;
 85             if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u])
 86             {
 87                 flag = true;
 88                 cur[u] = i;
 89                 break;
 90             }
 91         }
 92         if(flag)
 93         {
 94             S[top++] = cur[u];
 95             u = v;
 96             continue;
 97         }
 98         int Min = N;
 99         for(int i = head[u]; i != -1; i = edge[i].next)
100         if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)
101         {
102             Min = dep[edge[i].to];
103             cur[u] = i;
104         }
105         gap[dep[u]]--;
106         if(!gap[dep[u]])return ans;
107         dep[u] = Min + 1;
108         gap[dep[u]]++;
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
",ans);
152     }
153     return 0;
154 }