【HDUOJ】4280 Island Transport

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4280

题意：有n个岛屿,m条无向路,每个路给出最大允许的客流量,求从最西的那个岛屿最多能运用多少乘客到最东的那个岛屿

题解：最大流的裸题。输入记得找到最西和最东的岛屿，以及注意是双向边。。这题用的sap.

代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<cstdlib>

 #include<string>

 #include<queue>

 #include<algorithm>

 using namespace std;

 const int N=;

 const int M=;

 const int inf=0xfffffff;

 int n,m,cnt;

 struct Edge{

     int v , cap , next;

 } edge[M];

 int head[N],pre[N],d[N],numd[N];

 int cur_edge[N];

 void addedge(int u,int v,int c){

     edge[cnt].v = v;

     edge[cnt].cap = c;

     edge[cnt].next = head[u];

     head[u] = cnt++;

     edge[cnt].v = u;

     edge[cnt].cap = ;

     edge[cnt].next = head[v];

     head[v] = cnt++;

 }

 void bfs(int s){

     memset(numd,,sizeof(numd));

     for(int i=; i<=n; i++)    numd[ d[i] = n ]++;

     d[s] = ;

     numd[n]--;

     numd[]++;

     queue<int> Q;

     Q.push(s);

     while(!Q.empty()){

         int v=Q.front();

         Q.pop();

         int i=head[v];

         while(i != -){

             int u=edge[i].v;

             if(d[u]<n){

                 i=edge[i].next;

                 continue ;

             }

             d[u] = d[v]+;

             numd[n]--;

             numd[d[u]]++;

             Q.push(u);

             i=edge[i].next;

         }

     }

 }

 int SAP(int s,int t){

     for(int i = ; i <= n; i++)    cur_edge[i] = head[i];

     int max_flow = ;

     bfs(t);

     int u = s ;

     while(d[s] < n){

         if(u == t){

             int cur_flow = inf,neck;

             for(int from = s; from != t; from = edge[cur_edge[from]].v){

                 if(cur_flow > edge[cur_edge[from]].cap){

                     neck = from;

                     cur_flow = edge[cur_edge[from]].cap;

                 }

             }

             for(int from = s; from != t; from = edge[cur_edge[from]].v){    //修改增广路上的边的容量

                 int tmp = cur_edge[from];

                 edge[tmp].cap -= cur_flow;

                 edge[tmp^].cap += cur_flow;

             }

             max_flow += cur_flow;

             u = neck;

         }

         int i;

         for(i = cur_edge[u]; i != -; i = edge[i].next)

             if(edge[i].cap && d[u] == d[edge[i].v]+)

                 break;

         if(i != -){

             cur_edge[u] = i;

             pre[edge[i].v] = u;

             u = edge[i].v;

         }

         else{

             numd[d[u]]--;

             if(!numd[d[u]]) break;

             cur_edge[u] = head[u];

             int tmp = n;

             for(int j = head[u]; j != -; j = edge[j].next)

                 if(edge[j].cap && tmp > d[edge[j].v])

                     tmp = d[edge[j].v];

             d[u] = tmp+;

             numd[d[u]]++;

             if(u != s)

                 u = pre[u];

         }

     }

     return max_flow;

 }

 inline void pre_init(){

     cnt = ;

     memset(head, -, sizeof head);

 }

 void mapping(){

     int u, v, w;

     for(int i = ; i <= m; ++i){

         scanf("%d %d %d", &u, &v, &w);

         addedge(u, v, w);

         addedge(v, u, w);

     }

 }

 int main(){

     int tcase;

     scanf("%d",&tcase);

     while(tcase--){

         scanf("%d%d",&n,&m);

         int x,y,s,t;

         int minn = inf, maxx = -inf;

         for(int i = ; i <= n; i++){

             scanf("%d%d",&x,&y);

             if(x <= minn){

                 s = i;

                 minn = x;

             }

             if(x >= maxx){

                 t = i;

                 maxx = x;

             }

         }

         pre_init();

         mapping();

         int ans = SAP(s,t);

         printf("%d\n",ans);

     }

     return ;

 }