蒟蒻求助

PRXOR @ 2019-03-22 20:26:57

#include<bits/stdc++.h>
#define inf 9223300000000000000
#define nint long long
using namespace std;
int a[10011][10011],c[10011][10011],b[10011];
int n,m,s,t;
nint minn(int a,nint b)
{
    if(a<b) return a;
    else return b;
}
void bfs(int mi)
{
    queue<int> q;
    while(!q.empty()) q.pop();
    q.push(mi);
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=1;i<=n;i++)
        {
            if(a[now][i]!=0)
            {
                q.push(i);
                b[i]=min(b[i],b[now]+1);
            }
        }
    }
    return ;
}
nint dinic(int mi,nint money)
{
    /////////////////////////////////////
}
int main()
{
    memset(a,-1,sizeof(a));
    memset(b,0,sizeof(b));
    memset(c,-1,sizeof(c));
    cin>>n>>m>>s>>t;
    for(int i=0;i<m;i++)
    {
        int l,r,x;
        cin>>l>>r>>x;
        a[l][r]=x;
        c[l][r]=0;
    }
    bfs(s);
    cout<<dinic(s,inf);
    return 0;
}

by 花里心爱 @ 2019-03-22 20:29:45

你这么写真的对吗qwqwq

by Sai0511 @ 2019-03-22 20:42:36

bfs感觉不是很对呀

by Sai0511 @ 2019-03-22 20:43:53

#include <bits/stdc++.h>
#define il inline
const int maxn = 1e4 + 10;
const int maxm = 2e5 + 10;
const int inf = 0x3f3f3f3f;
using namespace std;
namespace Fast_Input {
    template<class T> il void read(T& res) {
        res = 0;char ch;bool sign = 0;
        do { ch = getchar(); sign |= ch == '-'; } while(!isdigit(ch));
        while(isdigit(ch)) {
            res = (res << 1) + (res << 3) + (ch & 15);
            ch = getchar();
        }
        (sign) && (res = -res);
    } 
}
using Fast_Input::read;
int n,m,i,j,k,s,t,ecnt = -1;
int head[maxn],depth[maxn];
int wei[maxm << 1],nxt[maxm << 1],ver[maxm << 1];
il int _min(int x,int y) {
    return x < y ? x : y;   
}
il void addedge(int u,int v,int w) {
    wei[++ecnt] = w;
    ver[ecnt] = v;
    nxt[ecnt] = head[u];
    head[u] = ecnt;
    return;
}
il bool bfs() {
    memset(depth,0,sizeof(depth));
    queue<int> q;q.push(s);depth[s] = 1;
    while(!q.empty()) {
        int u = q.front();q.pop();   
        for(int i = head[u];~i;i = nxt[i]) {
            int v = ver[i];        
            if(!depth[v] && wei[i] > 0) {
                depth[v] = depth[u] + 1;
                q.push(v);
            }
        }
    }
    return depth[t] > 0;
}
int dfs(int u,int flow) {
    if(u == t) return flow;  
    for(int i = head[u];~i;i = nxt[i]) {
        int v = ver[i],w = wei[i];
        if(depth[v] == depth[u] + 1 && w != 0) {
            int tmp = dfs(v,_min(w,flow));       
            if(tmp > 0) {
                wei[i] -= tmp;
                wei[i ^ 1] += tmp;
                return tmp;
            }
        }
    }
    return 0;
}
il int dinic() {
    int res = 0;
    while(bfs()) { 
        while(int t = dfs(s,inf)) res += t;   
    }
    return res;
}
int main() {
    read(n);read(m);read(s);read(t);
    memset(head,-1,sizeof(head));
    for(int i = 1,u,v,w;i <= m;i++) {
        read(u);read(v);read(w);
        addedge(u,v,w);
        addedge(v,u,0);
    }
    printf("%d\n",dinic());
    return 0;
}

by YZhe @ 2019-03-22 20:44:55

您的dfs呢

by Sai0511 @ 2019-03-22 20:45:22

哦，不，你的程序完全就是错的。。
dfs函数去哪了？。。。
还有a数组和b数组是什么鬼啊。。
建议将dinic彻底理解之后再来写代码