网络流的疑问(关于本题的建图)
查看原帖
网络流的疑问(关于本题的建图)
395825
AThls123楼主2023/3/9 17:28

我这样建图没有问题啊,但为什么会 T 爆了。

    for(int i=1;i<=n;++i){
        scanf("%lld",&val[i]);
        sum+=val[i];
    }
    LL qu=sum/n;
    for(int i=1;i<=n;++i){
        if(qu>val[i])g1.push_back(make_pair(i,qu-val[i]));
        if(qu<val[i])g2.push_back(make_pair(i,val[i]-qu));
    }
    int len1=g1.size()-1;
    int len2=g2.size()-1;
    for(int i=0;i<=len1;++i){
        int x=g1[i].first;
        LL z=g1[i].second;
        LL w=0;
        add(s,x,z,w);
    }
    for(int j=0;j<=len2;++j){
        int x=g2[j].first;
        LL z=g2[j].second;
        LL w=0;
        add(x,t,z,w);
    }
    for(int i=0;i<=len1;++i){
        for(int j=0;j<=len2;++j){
            int x=g1[i].first;
            int y=g2[j].first;
            LL z=g1[i].second;
            int x1=min(x,y),x2=max(x,y);
            LL w=min(abs(n-x2 + x1-1 + 1),abs(x2-x1));
            add(x,y,z,w);
        }
    }
2023/3/9 17:28
加载中...