原来我写了个假的dinic

P3376 【模板】网络最大流

Custlo0793 @ 2020-11-11 15:48:28

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#define min(a,b) a<b?a:b
#define N 10101
#define ll long long
#define inf 0x7fffffffffffffffll
using namespace std;
inline int read()
{
    int x=0;char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
}
int n,m,top=1,head[N],s,t,cur[N];
struct Node{
    int v;
    ll val;
    int next;
}node[200100];
inline void addedge(int u,int v,ll val)
{
    node[++top].v=v;
    node[top].val=val;
    node[top].next=head[u];
    head[u]=top;
}
int vis[N],dep[N];
bool bfs(int s,int t)
{
    memset(dep,0x3f,sizeof(dep));
    memset(vis,0,sizeof(vis));
    dep[s]=0;
    queue<int>q;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=node[i].next){
            int d=node[i].v;
            if(dep[d]>dep[u]+1&&node[i].val){
                dep[d]=dep[u]+1;
                q.push(d);
                if(d==t) return 1;
            }
        }
    }
    if(dep[t]!=0x3f3f3f3f)return 1;
    return 0;
}
int dfs(int u,ll flow)
{
    ll rlow=0,res=0,restflow=flow;
    if(u==t || flow==0) return flow;
    for(int i=cur[u];i!=-1;i=node[i].next)
    {
        cur[u]=i;
        if(flow<=0) break;
        int d=node[i].v;
        if(node[i].val&&dep[d]==dep[u]+1)
        {
            rlow=dfs(d,min(restflow,node[i].val));
            if(rlow)
            {
            node[i].val-=rlow;
            node[i^1].val+=rlow;
            res+=rlow;
            restflow-=rlow;
            if(!restflow) break;    
            }   
        }
    }
    return res; 
}
int dinic(int s,int t)
{
 int res=0;
 while(bfs(s,t))
 {
  for(int i=1;i<=n;i++)cur[i]=head[i];
  res+=dfs(s,inf);  
 }  
 return res;
} 
int main()
{
 memset(head,-1,sizeof(head));
 cin>>n>>m>>s>>t;
 for(int i=1;i<=m;i++)
 {
  int u,v;
  ll val;
  u=read();
  v=read();
  val=read();
  addedge(u,v,val);
  addedge(v,u,0);   
 }
 cout<<dinic(s,t);
 return 0;  
}

RT


by Custlo0793 @ 2020-11-11 15:49:33

求助!


by 幻影星坚强 @ 2020-11-11 15:50:22

res不该是long long吗


by Custlo0793 @ 2020-11-11 15:52:41

@幻影星坚强 大佬,写了long long还是WA


by 幻影星坚强 @ 2020-11-11 16:07:25

dinic函数不也应该是long long吗()


by 幻影星坚强 @ 2020-11-11 16:12:35

dfs也应该是long long()


by hater @ 2020-11-11 16:12:40

@Knuth_Morris_Pratt 好好看看还有哪里没有开ll


by Zxc200611 @ 2020-11-11 16:13:59

试试这个:

#define int long long
signed main()
...

by Zxc200611 @ 2020-11-11 16:14:24

@Knuth_Morris_Pratt


by Custlo0793 @ 2020-11-12 13:01:09

@Zxc200611 @hater @幻影星坚强 谢谢!!

--------------------此贴终结-------------------------------------------------------------------------------------------------------


|