$TLE$ $30$ 求助

回复帖子

@打伞的大姐姐 2018-11-28 13:55 回复

蒟蒻只能想到网络流……数学不好啊啊啊啊$QAQ$
难道我的网络流真的不可能改么$QwQ$

#include<cstdio>
#include<climits>
#include<cstring>
#include<algorithm>
#define ll long long
#define N 1000010
using namespace std;

const ll inf=INT_MAX;
struct node{ll x,y,c,d,next,other;}a[N*2];
ll len=0,n,st,ed,tot,ans=0;
ll list[N],last[N],head,tail,d[N];
bool v[N];

void ins(ll x,ll y,ll c,ll d)
//从x到y,流量为存货量c,费用为d
{
    a[++len].x=x;a[len].y=y;a[len].c=c;a[len].d=d;
    a[len].next=last[x];last[x]=len;

    a[++len].x=y;a[len].y=x;a[len].c=0;a[len].d=-d;
    a[len].next=last[y];last[y]=len;

    a[len].other=len-1;a[len-1].other=len;
}

bool bfs()
{
    memset(d,63,sizeof(d));d[ed]=0;
    memset(v,true,sizeof(v));v[ed]=false;
    ll head=1,tail=2;
    list[head]=ed;
    while(head!=tail)
    {
        ll x=list[head++];
        for(int i=last[x];i;i=a[i].next)
        {
            ll y=a[i].y;
            if(a[a[i].other].c>0 && d[y]>d[x]-a[i].d)
            {
                d[y]=d[x]-a[i].d;
                if(v[y])
                {
                    v[y]=false;
                    list[tail++]=y;
                    if(tail>n) tail=1;
                }
            }
        }
        if(head>n) head=1;
        v[x]=true;
    }
    if(d[st]!=d[ed+1]) return true;
    return false;
}

ll dfs(ll x,ll k)
{
    v[x]=false;
    if(x==ed)
    {
        v[x]=true;
        return k;
    }
    ll t=0,my;
    for(int i=last[x];i;i=a[i].next)
    {
        ll y=a[i].y;
        if(a[i].c>0 && d[y]==d[x]-a[i].d && v[y] && t<k)
        {
            my=dfs(y,min(a[i].c,k-t));
            t+=my;a[i].c-=my;a[a[i].other].c+=my;
            ans+=my*a[i].d;
        }
    }
    v[x]=true;
    return t;
}

int main()
{
    //freopen("candy3.in","r",stdin);
    scanf("%lld",&n);st=0;ed=n+1; 
    for(int i=1;i<=n;i++)
    {
        ll x;scanf("%lld",&x);
        ll l=i-1,r=i+1;
        if(l==0) l=n;
        if(r==n+1) r=1;//环 
        ins(i,l,inf,1);ins(i,r,inf,1);ins(st,i,x,0);
        tot+=x;
    }
    tot/=n;
    for(int i=1;i<=n;i++) ins(i,ed,tot,0);
    n+=2;//加上起点和终点 
    while(bfs()) dfs(st,inf);
    printf("%lld",ans);
    return 0;
}
@Venus 2018-11-28 19:14 回复 举报

@夜刀神十香ღ $1e6$诶 网络流是搞神魔捏……

$Dinic$的上界是$O(n^2m)$吖……虽然到不了上界但是$1e6$也过不了吖……

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。