洛谷P4016 负载平衡问题

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 using namespace std;
 7 #define MAXN 110
 8 struct Node{
 9     int u,v,w,c;
10     Node(){}
11     Node(int u,int v,int w,int c):u(u),v(v),w(w),c(c){}
12 }p[MAXN<<3];
13 struct Record{
14     int u,dis;
15     Record(){}
16     Record(int u,int dis):u(u),dis(dis){}
17     bool operator < (const Record & a) const{
18         return dis>a.dis;
19     }
20 };
21 int head[MAXN],Next[MAXN<<3],nums[MAXN],dis[MAXN],pre[MAXN],preNode[MAXN];
22 bool vis[MAXN];
23 int i,j,k,m,n,tot,sum;
24 void addNode(int u,int v,int w,int c){
25     p[++tot]=Node(u,v,w,c);
26     Next[tot]=head[u],head[u]=tot;
27     p[++tot]=Node(v,u,0,-c);
28     Next[tot]=head[v],head[v]=tot;
29 }
30 bool dijkstra(int src,int goal){
31     priority_queue<Record> mque;
32     while(!mque.empty()) mque.pop();
33     for(register int i=0;i<=n+1;i++) vis[i]=false,dis[i]=1000000000;
34     mque.push(Record(src,0));
35     vis[src]=true; dis[src]=0;
36     pre[src]=-1;
37     while(!mque.empty()){
38         Record tmp=mque.top(); mque.pop();
39         if(dis[tmp.u]<tmp.dis) continue;
40         //if(vis[tmp.u]) continue;
41         for(register int i=head[tmp.u];i+1;i=Next[i]){
42             if(p[i].w&&dis[tmp.u]+p[i].c<dis[p[i].v]){
43                 pre[p[i].v]=tmp.u;
44                 preNode[p[i].v]=i;
45                 dis[p[i].v]=dis[tmp.u]+p[i].c;
46                 mque.push(Record(p[i].v,dis[p[i].v]));
47             }
48         }
49     }
50     if(dis[goal]!=1000000000) return true;
51     return false;
52 }
53 int dinic(int src,int goal){
54     int ans=0;
55     while(dijkstra(src,goal)){
56         int minf=1000000000;
57         for(register int i=goal;i!=src;i=pre[i]){
58             minf=min(minf,p[preNode[i]].w);
59         }
60         for(register int i=goal;i!=src;i=pre[i]){
61             p[preNode[i]].w-=minf;
62             p[preNode[i]^1].w+=minf;
63         }
64         ans+=dis[goal]*minf;
65     }
66     return ans;
67 }
68 int main(){
69     scanf("%d",&n);
70     sum=0;
71     for(i=1;i<=n;i++) scanf("%d",nums+i),sum+=nums[i];
72     sum/=n;
73     for(i=0;i<=n+1;i++) head[i]=-1;
74     tot=-1;
75     for(i=1;i<=n;i++) nums[i]-=sum;
76     for(i=1;i<=n;i++) if(nums[i]>0) addNode(0,i,nums[i],0); else { if(nums[i]<0) addNode(i,n+1,-nums[i],0); }
77     for(i=1;i<=n-1;i++) addNode(i,i+1,10000000,1),addNode(i+1,i,10000000,1);
78     addNode(n,1,10000000,1),addNode(1,n,10000000,1);
79     printf("%d\n",dinic(0,n+1));
80     return 0;
81 }