# 洛谷P4016 负载平衡问题 费用流

Code:

```#include<cstdio>              //好题
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=500;
const int INF=1000000+23666;
typedef long long ll;
int A[maxn];
int s,t,n;
struct Edge{
int from,to,cap,cost;
Edge(int u,int v,int c,int f):from(u),to(v),cap(c),cost(f){}
};
struct MCMF{
vector<Edge>edges;
vector<int>G[maxn];
int d[maxn],inq[maxn],a[maxn],flow2[maxn];
queue<int>Q;
ll ans=0;
int flow=0;
void addedge(int u,int v,int c,int f){
edges.push_back(Edge(u,v,c,f));    //正向弧
edges.push_back(Edge(v,u,0,-f));   //反向弧
int m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
int SPFA(){
for(int i=0;i<=n;++i)d[i]=INF,flow2[i]=INF;
memset(inq,0,sizeof(inq));int f=INF;
d[s]=0,inq[s]=1;Q.push(s);
while(!Q.empty()){
int u=Q.front();Q.pop();inq[u]=0;
int sz=G[u].size();
for(int i=0;i<sz;++i){
Edge e=edges[G[u][i]];
if(e.cap>0&&d[e.to]>d[u]+e.cost){
a[e.to]=G[u][i];
d[e.to]=d[u]+e.cost;
flow2[e.to]=min(flow2[u],e.cap);
if(!inq[e.to]){inq[e.to]=1;Q.push(e.to);}
}
}
}
if(d[t]==INF)return 0;
f=flow2[t];
flow+=f;
int u=edges[a[t]].from;
edges[a[t]].cap-=f;
edges[a[t]^1].cap+=f;
while(u!=s){
edges[a[u]].cap-=f;
edges[a[u]^1].cap+=f;
u=edges[a[u]].from;
}
ans+=(ll)(d[t]*f);
return 1;
}
ll maxflow(){
while(SPFA());
return ans;
}
// ll getcost(){return ans;}
}op;
int main()
{
int N;scanf("%d",&N);
s=0,t=N+1,n=N+1;
int sum=0,ave;
for(int i=1;i<=N;++i){
int a;scanf("%d",&a);
A[i]=a;
sum+=a;
}
ave=sum/N;
for(int i=1;i<=N;++i)
{
int a=A[i]-ave;
}
for(int i=2;i<N;++i)
{
}
printf("%lld",op.maxflow());
return 0;
}
```

(0)
(0)

© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4