Island Transport

25 73 33 03 10 04 51 3 32 3 42 4 31 5 64 5 31 4 43 4 26 7-1 -10 10 21 01 12 31 2 12 3 64 5 55 6 31 4 62 5 53 6 4 Sample Output
96 ————————————————————————————————————題目的意思是給你n個(gè)點(diǎn)的坐標(biāo)和m條帶流量的無向邊求醉西邊島到最東邊島的最大流量思路：直接找出最西邊的島和最東邊的島作為源點(diǎn)和匯點(diǎn)，套最大流板子即可
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <queue>#include <vector>#include <stack>#include <set>#include <map>using namespace std;const int MAXN =100010;//點(diǎn)maxconst int MAXM=400010;//邊maxconst int INF=0x3f3f3f3f;struct Edge{int to,next,cap,flow;}edge[MAXM];int tol;int head[MAXN];int gap[MAXN],dep[MAXN],cur[MAXN];void init(){    tol=0;    memset(head,-1,sizeof(head));}void addedge(int u,int v,int w,int rw=0){    edge[tol].to=v;edge[tol].cap=w;edge[tol].flow=0;    edge[tol].next=head[u];head[u]=tol++;     edge[tol].to=u;edge[tol].cap=w;edge[tol].flow=0;    edge[tol].next=head[v];head[v]=tol++;}int Q[MAXN];void BFS(int start,int end){    memset(dep,-1,sizeof(dep));    memset(gap,0,sizeof(gap));    gap[0]=1;    int front=0,rear=0;    dep[end]=0;    Q[rear++]=end;    while(front!=rear)    {        int u=Q[front++];        for(int i=head[u];i!=-1;i=edge[i].next)        {            int v=edge[i].to;            if(dep[v]!=-1)                continue;            Q[rear++]=v;            dep[v]=dep[u]+1;            gap[dep[v]]++;        }    }}int S[MAXN];int sap(int start,int end,int N){    BFS(start,end);    memcpy(cur,head,sizeof(head));    int top=0;    int u =start;    int ans=0;    while(dep[start]<N)    {        if(u==end)        {            int Min=INF;            int inser;            for(int i=0;i<top;i++)            {                if(Min>edge[S[i]].cap-edge[S[i]].flow)                {                    Min=edge[S[i]].cap-edge[S[i]].flow;                    inser=i;                }            }            for(int i=0;i<top;i++)            {                edge[S[i]].flow+=Min;                edge[S[i]^1].flow-=Min;            }            ans+=Min;            top=inser;            u=edge[S[top]^1].to;            continue;        }        bool flag=false;        int v;        for(int i=cur[u];i!=-1;i=edge[i].next)        {            v=edge[i].to;            if(edge[i].cap-edge[i].flow&&dep[v]+1==dep[u])            {                flag=true;                cur[u]=i;                break;            }        }        if(flag)        {            S[top++]=cur[u];            u=v;            continue;        }        int Min=N;        for(int i=head[u];i!=-1;i=edge[i].next)        {            if(edge[i].cap-edge[i].flow&&dep[edge[i].to]<Min)            {                Min=dep[edge[i].to];                cur[u]=i;            }        }        gap[dep[u]]--;        if(!gap[dep[u]])return ans;        dep[u]=Min+1;        gap[dep[u]]++;        if(u!=start)            u=edge[S[--top]^1].to;    }    return ans;}int main(){   int n,m,u,v,w,c;   int T;  while(~scanf("%d",&T))  {      while(T--)      {          init();          scanf("%d%d",&n,&m);          int w=999999,e=-999999,st,ed;          for(int i=1;i<=n;i++)          {              scanf("%d%d",&u,&v);              if(w>u)              {                   w=u;                   st=i;              }              if(u>e)               {                   e=u;                   ed=i;               }          }          for(int i=0;i<m;i++)          {              scanf("%d%d%d",&u,&v,&c);              addedge(u,v,c,0);          }          printf("%d/n",sap(st,ed,n));      }  }    return 0;}