前言
网络流 24 题还是要写一下.
Solution
我们先来研究一下这个题目是个什么东西:
每一个点有可能比平均数多, 也有可能少, 然后你就发现相当于是我们建了两个超级源点和超级汇点, 然后从这两个点去分和流入.
然后对于这个环就可以直接建环 (注意建边的时候的一些细节操作)
跑一边费用流就好了.
- #include<stdio.h>
- #include<stdlib.h>
- #include<string.h>
- #include<math.h>
- #include<algorithm>
- #include<queue>
- #include<set>
- #include<map>
- #include<iostream>
- using namespace std;
- #define ll long long
- #define re register
- #define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
- inline int gi(){
- int f=1,sum=0;char ch=getchar();
- while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
- while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
- return f*sum;
- }
- const int N=5010,M=50010,Inf=1e9+10;
- int n,s,t,MaxFlow,MinCost,a[N];
- class Graph{
- private:
- int front[N],cnt,nxt[M<<1],to[M<<1],w[M<<1],c[M<<1],dis[N],vis[N],fa[N],from[N];
- bool SPFA(){
- queue<int>Q;while(!Q.empty())Q.pop();
- Q.push(s);memset(dis,127,sizeof(dis));vis[s]=1;dis[s]=0;
- while(!Q.empty()){
- int u=Q.front();Q.pop();vis[u]=0;
- for(int i=front[u];i!=-1;i=nxt[i]){
- int v=to[i];
- if(w[i] && dis[v]>dis[u]+c[i]){
- dis[v]=dis[u]+c[i];from[v]=i;fa[v]=u;
- if(!vis[v]){
- vis[v]=1;Q.push(v);
- }
- }
- }
- }
- return dis[t+1]!=dis[t];
- }
- void add(int u,int v,int val,int f){to[cnt]=v;nxt[cnt]=front[u];front[u]=cnt;w[cnt]=val;c[cnt]=f;++cnt;}
- public:
- void Add(int u,int v,int val,int f){add(u,v,val,f);add(v,u,0,-f);}
- void init(){memset(front,-1,sizeof(front));cnt=0;}
- void Solve(){
- while(SPFA()){
- int d=Inf;
- for(int i=t;i!=s;i=fa[i])d=min(d,w[from[i]]);
- MaxFlow+=d;MinCost+=d*dis[t];
- for(int i=t;i!=s;i=fa[i]){w[from[i]]-=d;w[from[i]^1]+=d;}
- }
- }
- }MfMc;
- int main(){
- n=gi();int sum=0;MfMc.init();
- for(int i=1;i<=n;i++){a[i]=gi();sum+=a[i];}
- sum/=n;s=0;t=n+1;
- for(int i=1;i<=n;i++)a[i]-=sum;
- for(int i=1;i<=n;i++)
- if(a[i]>0)MfMc.Add(s,i,a[i],0);
- else if(a[i]<0)MfMc.Add(i,t,-a[i],0);
- for(int i=1;i<=n;i++){
- if(i!=1)MfMc.Add(i,i-1,Inf,1);
- if(i!=n)MfMc.Add(i,i+1,Inf,1);
- }
- MfMc.Add(1,n,Inf,1);
- MfMc.Add(n,1,Inf,1);
- MfMc.Solve();
- printf("%d\n",MinCost);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2915913.html