社区讨论
嘤嘤嘤!可爱的萌新求救!
P4016负载平衡问题参与者 8已保存回复 19
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 19 条
- 当前快照
- 1 份
- 快照标识符
- @mi7pr1ss
- 此快照首次捕获于
- 2025/11/21 01:36 4 个月前
- 此快照最后确认于
- 2025/11/21 01:53 4 个月前
RT
只过了一个点,查不出哪里错了qwq
CPP#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=505;
int vis[maxn],head[maxn],dist[maxn],pre[maxn],last[maxn],flow[maxn],cc[maxn];
int n,m,T,S,maxflow,mincost,cnt=-1;
struct node{
int to,next,flw,dis;
}e[maxn];
queue<int>q;
void add(int x,int y,int f,int d){
e[++cnt].next=head[x];
e[cnt].to=y;
e[cnt].flw=f;
e[cnt].dis=d;
head[x]=cnt;
}
bool spfa(int s,int t){
memset(dist,63,sizeof(dist));
memset(flow,127,sizeof(flow));
memset(vis,0,sizeof(vis));
while(!q.empty())q.pop();
q.push(s);vis[s]=1;dist[s]=0;pre[t]=-1;
while(!q.empty()){
int h=q.front();
q.pop();vis[h]=0;
for(int i=head[h];i!=-1;i=e[i].next){
if(e[i].flw>0&&dist[e[i].to]>dist[h]+e[i].dis){
dist[e[i].to]=dist[h]+e[i].dis;
pre[e[i].to]=h;
last[e[i].to]=i;
flow[e[i].to]=min(flow[h],e[i].flw);
if(!vis[e[i].to]){
vis[e[i].to]=1;
q.push(e[i].to);
}
}
}
}return pre[t]!=-1;
}
void MCMF(){
while(spfa(S,T)){
int h=T;
maxflow+=flow[T];
mincost+=flow[T]*dist[T];
while(h!=S){
e[last[h]].flw-=flow[T];
e[last[h]^1].flw+=flow[T];
h=pre[h];
}
}
}
void ccll(){
for(int i=2;i<n;i++){
add(i,i+1,1e9,1);
add(i,i-1,1e9,1);
add(i+1,i,0,-1);
add(i-1,i,0,-1);
}
add(1,2,1e9,1);
add(1,n,1e9,1);
add(2,1,0,-1);
add(n,1,0,-1);
add(n,1,1e9,1);
add(n,n-1,1e9,1);
add(n-1,n,0,-1);
add(1,n,0,-1);
}
int main(){
int cl=0;
cin>>n;
for(int i=1;i<=n;i++)cin>>cc[i],cl+=cc[i];
cl/=n;S=0;T=n+1;
memset(head,-1,sizeof(head));
for(int i=1;i<=n;i++){
if(cc[i]>cl){
add(S,i,cc[i]-cl,0);
add(i,S,0,0);
}
if(cc[i]<cl){
add(i,T,cl-cc[i],0);
add(T,i,0,0);
}
}
ccll();
MCMF();
cout<<mincost;
}
回复
共 19 条回复,欢迎继续交流。
正在加载回复...