网上做名片的网站,淘宝官网首页手机版,玉山网站建设,合肥大型网站设计求出平均数sum#xff0c;对于大于sum的点连接(s,i,a[i]-sum,0)#xff0c;表示这个点可以流出多余的部分#xff0c;对于小于sum的点连接(i,t,sum-a[i],0)表示这个点可以接受少的部分#xff0c;然后每个点向相邻的两个点连(i,j,inf,1)表示可以任意转移#xff0c;每转移…求出平均数sum对于大于sum的点连接(s,i,a[i]-sum,0)表示这个点可以流出多余的部分对于小于sum的点连接(i,t,sum-a[i],0)表示这个点可以接受少的部分然后每个点向相邻的两个点连(i,j,inf,1)表示可以任意转移每转移一份产生1费用注意这是个环所以首尾相连。然后跑最小费用最大流即可。 #includeiostream
#includecstdio
#includequeue
#includecstring
using namespace std;
const int N1000005,inf1e9;
int n,h[N],cnt1,dis[N],fr[N],ans,s,t,a[105],sum;
bool v[N];
struct qwe
{int ne,no,to,va,c;
}e[N2];
int read()
{int r0,f1;char pgetchar();while(p9||p0){if(p-)f-1;pgetchar();}while(p0p9){rr*10p-48;pgetchar();}return r*f;
}
void add(int u,int v,int w,int c)
{cnt;e[cnt].neh[u];e[cnt].nou;e[cnt].tov;e[cnt].vaw;e[cnt].cc;h[u]cnt;
}
void ins(int u,int v,int w,int c)
{//coutu v wendl;add(u,v,w,c);add(v,u,0,-c);
}
bool spfa()
{queueintq;for(int is;it;i)dis[i]inf;dis[s]0;v[s]1;q.push(s);while(!q.empty()){int uq.front();q.pop();v[u]0;for(int ih[u];i;ie[i].ne)if(e[i].va0dis[e[i].to]dis[u]e[i].c){dis[e[i].to]dis[u]e[i].c;fr[e[i].to]i;if(!v[e[i].to]){v[e[i].to]1;q.push(e[i].to);}}}return dis[t]!inf;
}
void mcf()
{//coutOKendl;int xinf;for(int ifr[t];i;ifr[e[i].no])xmin(x,e[i].va);for(int ifr[t];i;ifr[e[i].no]){e[i].va-x;e[i^1].vax;ansx*e[i].c;}
}
int main()
{nread();for(int i1;in;i)a[i]read(),suma[i];s0,tn1;sum/n;for(int i1;in;i){if(a[i]sum)ins(s,i,a[i]-sum,0);elseins(i,t,sum-a[i],0);}for(int i1;in;i){ins(i,(i1n)?1:i1,inf,1);ins(i,(i-11)?n:i-1,inf,1);}while(spfa())mcf();printf(%d\n,ans);return 0;
} 转载于:https://www.cnblogs.com/lokiii/p/8441215.html
