社区讨论

蜜汁错误,孩子人都傻了

P1251餐巾计划问题参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@locpxkoa
此快照首次捕获于
2023/10/30 17:49
2 年前
此快照最后确认于
2023/11/05 04:39
2 年前
查看原帖
找了一阵子不知道哪错了?建图和模板都应该没错,但是样例都不对。。。emmm求大佬看看
CPP
#include<bits/stdc++.h>
#define mem(x,a) memset(x,a,sizeof(x))
#define inf 1e9+7
typedef long long ll;
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
   return s*w;
}
const int maxn=3e5+9;
struct node{
	int u,v,w,next,dis;
}edge[maxn];
int cnt=1,head[maxn];
int a[maxn];
void add_edge(int u,int v,int w,int dis)
{
	edge[++cnt].v=v;
	edge[cnt].w=w;
	edge[cnt].next=head[u];
	edge[cnt].dis=dis;
	head[u]=cnt;
}
void add(int u,int v,int w,int dis)
{
	add_edge(u,v,w,dis);
	add_edge(v,u,0,-dis);
}
int flow[maxn],dis[maxn],link[maxn],vis[maxn],pre[maxn];
int n,S=0,T=2*n+1,p,m,f,w,s;
bool spfa()
{
	mem(vis,0);
	mem(dis,0x3f3f3f);
	mem(pre,-1);
	queue<int>q;
	vis[S]=1;
	dis[S]=0;
	pre[S]=0;
	flow[S]=inf;
	q.push(S);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=edge[i].next)
		{
			int v=edge[i].v;
			int w=edge[i].w;
			int d=edge[i].dis;
			if(w>0&&dis[v]>dis[u]+d)
			{
				dis[v]=dis[u]+d;
				pre[v]=u;
				link[v]=i;
				flow[v]=min(flow[u],w);
				if(!vis[v])
				{
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
	return pre[T]!=-1;
}
inline int mcmf()
{
	int sum=0;
	while(spfa())
	{
		int k=T;
		while(k!=S)
		{
			edge[link[k]].w-=flow[T];
			edge[link[k]^1].w+=flow[T];
			k=pre[k];
		}
		sum+=flow[T]*dis[T];
	}
	return sum;
}
int main()
{
	cin>>n;
	cin>>p>>m>>f>>w>>s;
	/*
	p 是每块新餐巾的费用;
	mm 是快洗部洗一块餐巾需用天数; 
	ff 是快洗部洗一块餐巾需要的费用;
	w 是慢洗部洗一块餐巾需用天数;
	ss 是慢洗部洗一块餐巾需要的费用。
	*/
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		add(S,i,a[i],0);
	}
	for(int i=1;i<=n;i++)
	{
		if(i+m<=n)add(i,i+n+m,inf,f);
		if(i+w<=n)add(i,i+n+w,inf,s);
		if(i+1<=n)add(i,i+1,inf,0);
		add(i+n,T,a[i],0);
		add(S,i+n,inf,p);
	}
	cout<<mcmf()<<endl;
}	

回复

2 条回复,欢迎继续交流。

正在加载回复...