社区讨论

嘤嘤嘤!可爱的萌新求救!

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 条回复,欢迎继续交流。

正在加载回复...