【最大流】【CODEVS】1993 草地排水

不念不忘少年蓝@ 2022-01-12 01:19 140阅读 0赞

【算法】网络流-最大流(dinic)

【题解】http://www.cnblogs.com/onioncyc/p/6496532.html

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    const int maxn=210,inf=0x3f3f3f3f;
    struct edge{
         int from,v,flow;}e[maxn*3];
    int n,m,tot=2,S,T,d[maxn],q[510],first[maxn],cur[maxn];
    void insert(int u,int v,int flow)
    {tot++;e[tot].v=v;e[tot].flow=flow;e[tot].from=first[u];first[u]=tot;}
    bool bfs()
    {
        memset(d,-1,sizeof(d));
        int head=0,tail=1;q[head]=S;
        d[S]=0;
        while(head!=tail)
         {
             int x=q[head++];if(head>=501)head=0;
             for(int i=first[x];i;i=e[i].from)
             if(d[e[i].v]==-1&&e[i].flow>0)
              {
                  q[tail++]=e[i].v;d[e[i].v]=d[x]+1;
                  if(tail>=501)tail=0;
              }
         }
        if(d[T]==-1)return 0;else return 1;
    }
    int dfs(int x,int a)
    {
        if(x==T||a==0)return a;
        int flow=0,f;
        for(int& i=cur[x];i;i=e[i].from)//当前弧优化 
         if(d[e[i].v]==d[x]+1&&(f=dfs(e[i].v,min(a,e[i].flow)))>0)
          {
              e[i].flow-=f;
              e[i^1].flow+=f;
              flow+=f;
              a-=f;
              if(a==0)break;
          }
        return flow;
    }
    int main()
    {
        scanf("%d%d",&m,&n);
        S=1;T=n;
        for(int i=1;i<=m;i++)
         {
             int u,v,w;
             scanf("%d%d%d",&u,&v,&w);
             insert(u,v,w);
             insert(v,u,0);
         }
        int ans=0;
        while(bfs())
         {
             for(int i=1;i<=n;i++)cur[i]=first[i];
             ans+=dfs(S,inf);
         }
        printf("%d",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/onioncyc/p/6421652.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220109/41f854a05d9340f1ad82a4dc25ac87a6.png