网络流24题——负载平衡问题

题目描述

建模分析：

首先先计算出他们的平均数,用每个数都减去平均数得到新的值,这个值如果是负数意味着需要从别的地方搞过一点来,如果正数就说明可以往外送一点.

我们建立超级源点和超级汇点(这套路很常见的)

如果权值为正,即储存量大于平均值,我们就从s向它连一条边,最大流为：储存值-平均值,费用为0,图论意义就是它可以从源点免费获得多出来的储存值-平均值的流量,就相当于自身有储存值-平均值的流量,上面不是说了吗,建一个超级源点,就是代替这个功能.

如果权值为负,即储存值小于平均值,我们就从它向t连一条边,最大流量为平均值-储存值,费用为0,图论意义就是它必须从别的节点传来流量,并且汇入自身,意义类比与上面所说.

对于每一个可以互相传的节点,即左邻居和右邻居,需要分别向他们连边,表示自己的流可以流过去.

这是单点做法，还可以拆点，还有贪心做法，可参见均分纸牌。

代码：

 1 #include<bits/stdc++.h>
 2 #define INF 2147483647
 3 using namespace std;
 4 queue<int> q;
 5 int n,m,len,st,ed,ans;
 6 struct node
 7 {int x,y,c,d,next;} a[10000];
 8 int b[10000],last[10000],dis[10000],pre[10000],pos[10000],p[10000];
 9 bool vis[10000];
10 void ins(int x,int y,int c,int d)
11 {
12     a[len].y=y;
13     a[len].c=c;
14     a[len].d=d;
15     a[len].next=last[x];
16     last[x]=len++;
17 }
18 bool spfa()
19 {
20     memset(dis,63,sizeof(dis));
21     memset(vis,0,sizeof(vis));
22     vis[st]=1,dis[st]=0,q.push(st),p[st]=INF,pos[ed]=0;
23     while (!q.empty())
24     {
25         int u=q.front();q.pop();
26         vis[u]=0;
27         for (int i=last[u];i!=-1;i=a[i].next)
28         {
29             int ne=a[i].y;
30             if (a[i].c&&dis[ne]>dis[u]+a[i].d)
31             {
32                 dis[ne]=dis[u]+a[i].d;
33                 pos[ne]=u;
34                 pre[ne]=i;
35                 p[ne]=min(p[u],a[i].c);
36                 if (!vis[ne])
37                 {
38                     vis[ne]=1;
39                     q.push(ne);
40                 }
41             }
42         }
43     }
44     return pos[ed]!=0;
45     //return dis[ed]<1061109567;
46 }
47 void dinic()
48 {
49     while (spfa())
50     {
51         ans+=p[ed]*dis[ed];
52         for (int i=ed;i!=st;i=pos[i])
53         {
54             a[pre[i]].c-=p[ed];
55             a[pre[i]^1].c+=p[ed];
56         }
57     }
58 }
59 int main()
60 {
61     int sum=0;
62     scanf("%d",&n);
63     st=0;ed=n+1;
64     for(int i=1;i<=n;i++)
65     {
66         scanf("%d",&b[i]);
67         sum+=b[i];
68     }
69     sum/=n;
70     memset(last,-1,sizeof(last));
71     for(int i=1;i<=n;i++)
72         if(b[i]>sum)
73             ins(st,i,b[i]-sum,0),ins(i,st,0,0);
74         else
75             ins(i,ed,sum-b[i],0),ins(ed,i,0,0);
76     for(int i=2;i<=n;i++)
77     {
78         ins(i-1,i,INF,1),ins(i,i-1,0,-1);
79         ins(i,i-1,INF,1),ins(i-1,i,0,-1);
80     }
81     ins(1,n,INF,1),ins(n,1,0,-1);
82     ins(n,1,INF,1),ins(1,n,0,-1);
83     dinic();
84     printf("%d",ans);
85 }

View Code