社区讨论
蜜汁错误,孩子人都傻了
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 条回复,欢迎继续交流。
正在加载回复...