# $TLE$ $30$ 求助

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

#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;
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;
{
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;
}
}
}
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$也过不了吖……