社区讨论

T了7个点,求助(刚学OI)

P1361小M的作物参与者 9已保存回复 13

讨论操作

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

当前回复
13 条
当前快照
1 份
快照标识符
@mi86l660
此快照首次捕获于
2025/11/21 09:28
4 个月前
此快照最后确认于
2025/11/21 09:55
4 个月前
查看原帖
EK代码:
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll he[1000000],en[10000000],ed[10000000],ne[10000000],vi[1000000],mi[1000000],lu[1000000];
ll T,n,m,s,t,x,y,ans,c,tot,k,l,sum,o,p,a,b;
char r;
void add(ll x,ll y,ll z)
{
	en[++tot]=y,ed[tot]=z,ne[tot]=he[x],he[x]=tot;
	en[++tot]=x,ed[tot]=0,ne[tot]=he[y],he[y]=tot;
}
bool bfs()
{
	memset(vi,0,sizeof(vi));
	queue<ll> q;
	q.push(s);
	vi[s]=1;
	mi[s]=10000000;
	while(!q.empty())
	{
		x=q.front();
		q.pop();
		for(ll i=he[x];i;i=ne[i])
		{
			if(ed[i])
			{
				y=en[i];
				if(vi[y])continue;
				mi[y]=min(mi[x],ed[i]);
				lu[y]=i;
				q.push(y);
				vi[y]=1;
				if(y==t)return 1;
			}
		}
	}
	return 0;	
}
void up()
{
	x=t;
	while(x!=s)
	{
		y=lu[x];
		ed[y]-=mi[t];
		ed[y^1]+=mi[t];
		x=en[y^1];
	}
	ans+=mi[t];
}
int main()
{
	tot=1;
	scanf("%lld",&n);
	s=n+1;
	t=n+2;
	for(ll i=1;i<=n;i++)
	{
		scanf("%lld",&a);
		sum+=a;
		add(s,i,a);
	}
	for(ll i=1;i<=n;i++)
	{
		scanf("%lld",&b);
		sum+=b;
		add(i,t,b);
	}
	cin>>m;
	for(ll i=1;i<=m;i++)
	{
		scanf("%lld",&k);
		scanf("%lld%lld",&o,&p);
		sum+=o;
		sum+=p;
		add(s,n+i+2,o);
		add(n+m+i+2,t,p);
		for(ll j=1;j<=k;j++)
		{
			cin>>l;
			add(l,i+m+n+2,100000000);
			add(n+i+2,l,100000000);
		}
	}
	while(bfs())up();
	printf("%lld\n",sum-ans);
}
这题卡EK吗?
或是还能优化?
尤佳骏 Sumer_Light Mist_Stalker

回复

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

正在加载回复...