求助 dinic pt=70差不出错了QAQ

P3376 【模板】网络最大流

Dusker @ 2019-01-28 20:47:26

#include<bits/stdc++.h>
#define re register

using namespace std;

const int mmax=1e6+10;
const int inf=2147483647;

struct node
{
    int from,to,cap;
}edge[mmax];

int tot,first[mmax],m,n,s,t;
int dis[mmax];

inline int Min(const int &x,const int &y) {return x<y?x:y;}

inline void add(int x,int y,int z)
{
    edge[++tot].to=y;
    edge[tot].cap=z;
    edge[tot].from=first[x];
    first[x]=tot;
    return;
}

inline bool bfs()
{
    memset(dis,0,sizeof(dis));
    queue<int> q;
    dis[s]=1;q.push(s);
    while(!q.empty())
      {
        int u=q.front();q.pop();
        for(re int i=first[u];i;i=edge[i].from)
          if(!dis[edge[i].to] && edge[i].cap)
            dis[edge[i].to]=dis[u]+1,q.push(edge[i].to);
      }
    return dis[t];
}

int dfs(int cur,int maxf)
{
    if(cur == t || !maxf) return maxf;
    int flow=0,f;
    for(re int i=first[cur];i;i=edge[i].from)
      if(dis[edge[i].to] == dis[cur]+1 && (f=dfs(edge[i].to,Min(edge[i].cap,maxf))))
        {
            edge[i].cap-=f;
            edge[i^1].cap+=f;
            maxf-=f;
            flow+=f;
            if(!maxf) break;
        }
    return flow;
}

inline int dinic()
{
    int ans=0;
    while(bfs()) ans+=dfs(s,inf);
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>s>>t;
    for(re int i=1;i<=m;i++)
      {
        int x,y,s;
        cin>>x>>y>>s;
        add(x,y,s);
        add(y,x,0);
      }
    cout<<dinic();
}

by yurzhang @ 2019-01-28 20:51:02

tot初值赋1


by HrlAcc @ 2019-01-28 20:54:14

TSLzwy大佬


by 鸾辂音尘远 @ 2019-01-28 20:54:45

QAQ tql


by RiverFun @ 2019-01-28 20:54:45

@Dusk_Till_Dawn tot = 1


by qushi @ 2019-01-28 20:56:35

刚给我们讲过去你咋就不会拉?


by Dusker @ 2019-01-28 20:57:42

蟹蟹qaq


by Dusker @ 2019-01-28 20:57:58

@qushi 我在梦游 你别管我((


by yurzhang @ 2019-01-28 21:00:57

你这反边全找错了怎么拿的70分。。


by qushi @ 2019-01-28 21:02:43

@Dusk_Till_Dawn 你长那么胖游不起来的


by t162 @ 2019-01-29 11:11:59

@yurzhang 窝反边全找错噎是七十分。。。


|