本文共 2120 字，大约阅读时间需要 7 分钟。
//http://www.cnblogs.com/IMGavin/#include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;#define gets(A) fgets(A, 1e8, stdin)const int INF = 0x3F3F3F3F, N = 1008, MOD = 1003, M = 100000;int a[N];const double EPS = 1e-6;struct Node{ int u, v, cap, cost; int next;}edge[M];//有向图，u到v的容量，费用int tot;int head[N], pre[N], path[N], dis[N];bool inq[N];void init(){ tot = 0; memset(head, -1, sizeof(head));}void add(int u, int v, int cap, int cost){ edge[tot].u = u; edge[tot].v = v; edge[tot].cap = cap; edge[tot].cost = cost; edge[tot].next = head[u]; head[u] = tot++; edge[tot].u = v; edge[tot].v = u; edge[tot].cap = 0; edge[tot].cost = -cost; edge[tot].next = head[v]; head[v] = tot++;}bool SPFA(int st, int des){//计算最小费用 memset(inq, 0, sizeof(inq)); memset(dis, 0x3f, sizeof(dis)); queue q; q.push(st); dis[st] = 0; inq[st] = true; while(!q.empty()){ int u = q.front(); q.pop(); inq[u] = false; for(int i = head[u]; ~i; i = edge[i].next){ int v = edge[i].v; if(edge[i].cap > 0 && dis[v] > dis[u] + edge[i].cost){ dis[v] = dis[u] + edge[i].cost; pre[v] = u; path[v] = i; if(!inq[v]){ inq[v] = true; q.push(v); } } } } return dis[des] < INF;}int EdmondsKarp(int st, int des){//最小费用最大流 int mincost = 0, flow = 0;//最小费用与流量 while(SPFA(st, des)){ int f = INF; for(int i = des; i != st; i = pre[i]){ if(f > edge[path[i]].cap){ f = edge[path[i]].cap; } } for(int i = des; i != st; i = pre[i]){ edge[path[i]].cap -= f; edge[path[i]^1].cap += f; } mincost += f * dis[des]; flow += f; } return mincost;}int main(){ int n; while(cin >> n){ int st = 0, des = n + 1; int sum = 0; for(int i = 1; i <= n; i++){ cin >> a[i]; sum += a[i]; } init(); sum /= n; for(int i = 1; i <= n; i++){ if(a[i] < sum){ add(st, i, sum - a[i], 0); }else{ add(i, des, a[i] - sum, 0); } add(i, i % n + 1, INF, 1); add(i, (i - 2 + n) % n + 1, INF, 1); } printf("%d\n", EdmondsKarp(st, des)); } return 0;}
转载于:https://www.cnblogs.com/IMGavin/p/6411447.html