洛谷IDE和本地都没有RE,提交上去全RE
查看原帖
洛谷IDE和本地都没有RE,提交上去全RE
362243
Small_Tang楼主2022/10/12 22:03

rt,心态已经炸了,下载了第一个数据点,是没有问题的,本地和IDE上都正确。希望大佬能帮忙指出错误qwq。ps:第一个数据点是样例

#include<bits/stdc++.h>
#define dg(a) ((a)<'0'||(a)>'9')
#define Maxn 20000000009
#define int long long
#define Max 5009
using namespace std;

bool vis[Max];
int len=-1,lst[Max]; // 建边先 ++len ,所以相当于下标从零开始 
int h[Max],flow,st,ed;
int pw,f1,f2,d1,d2,n,a[Max];

struct node{int id,x;};
bool operator <(node _a,node _b){_a.x<_b.x;}
struct edge{int x,y,c,w,nxt;}p[Max<<4];

void read(int &r)
{
	r=0;char ch='t',f;ch=getchar();
	while(dg(ch)){f=ch;ch=getchar();}
	while(!dg(ch)){r=(r<<3)+(r<<1)+ch-'0';ch=getchar();}
	if(f=='-')r=-r;
}

void ins(int x,int y,int c,int w)
{
	len++; 
	p[len].x=x;p[len].y=y;
	p[len].c=c;p[len].w=w;
	p[len].nxt=lst[x];lst[x]=len;
}


bool bfs()
{
	int u=Maxn*100000;
	for(int i=0;i<=ed;i++)h[i]=u;
	h[st]=0;
	node t;t.id=st,t.x=0;
	priority_queue<node>q;q.push(t);
    while(!q.empty())
    {
        int x=q.top().id;q.pop();vis[x]=0;
        for(int k=lst[x];k!=-1;k=p[k].nxt)
        {
            int y=p[k].y;
            if(h[y]>h[x]+p[k].w&&p[k].c>(int)0)
            {
                h[y]=h[x]+p[k].w;
                if(!vis[y])
                {
                    vis[y]=1;
                    t.id=y;t.x=h[y];
                    q.push(t);
                }
            }
        }
    }
	return h[ed]!=h[0];
}

int dinic(int x,int w)
{
	if(x==ed)return w;
	int s=0;vis[x]=1;
	for(int k=lst[x];k!=-1;k=p[k].nxt)
	{
		int y=p[k].y;
		if(h[y]==h[x]+p[k].w&&p[k].c>(int)0&&s<w&&!vis[y])
		{
			int t=dinic(y,min(w-s,p[k].c));
			s+=t;
			flow+=t*p[k].w;
			p[k].c-=t;p[k^1].c+=t;
		}
	}
	vis[x]=0;
	if(s==0)h[x]=0;
	return s;
}

signed main()
{
	read(n);
	st=2*n+1;ed=st+1;
	memset(lst,-1,sizeof(lst));
	for(int i=1;i<=n;i++)
	{
		int x;read(x);a[i]=x;
		ins(st,i+n,x,0);ins(i+n,st,0,0);//还回统计过的衣服 
		ins(i,ed,x,0);ins(ed,i,0,0);//去统计衣服 
	}
	read(pw);
	read(d1);read(f1);read(d2);read(f2);
	for(int i=1;i<=n-d1;i++)
	{
		ins(i+n,i+d1,Maxn,f1);//快洗 
		ins(i+d1,i+n,0,-f1);
	}
	for(int i=1;i<=n-d2;i++)
	{
		ins(i+n,i+d2,Maxn,f2);//慢洗 
		ins(i+d2,i+n,0,-f2);
	}
	for(int i=1;i<n;i++)
	{
		ins(st,i,a[i],pw);ins(i,st,0,-pw);//买餐巾
		ins(i+n,i+n+1,Maxn,0);//留盘子 
		ins(i+n+1,i+n,0,0);
	}
	ins(st,n,a[n],pw);ins(n,st,0,-pw); 
	int ans=0;
	while(bfs())ans+=dinic(st,Maxn*1000);
	printf("%lld",flow);
	return 0;
}
2022/10/12 22:03
加载中...