我当前弧优化也加了,快读也加了,但过不过就是另一回事了
  • 板块P1361 小M的作物
  • 楼主_maze
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/12/4 09:20
  • 上次更新2023/11/5 06:45:28
查看原帖
我当前弧优化也加了,快读也加了,但过不过就是另一回事了
149219
_maze楼主2020/12/4 09:20

8个TLE,实在不知道为什么了。。。

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
int to[4000005],nx[4000005],st[4000005],zhi[4000005],tot=1;
int num;
void add(int u,int v,int w){
	to[++tot]=v;
	zhi[tot]=w;
	nx[tot]=st[u];
	st[u]=tot;
}
int c[4000005],ceng[4000005];
bool bfs(int s){
	for(int i=0;i<=num;i++)ceng[i]=-1;
	ceng[s]=0;
	for(int i=0;i<=num;i++) c[i]=st[i];
	queue<int> q;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=c[u];i;i=nx[i]){
			int v=to[i];
			if(zhi[i]>0&&ceng[v]==-1){
				ceng[v]=ceng[u]+1;
				q.push(v);
			}
		}
	}
	if(ceng[t]==-1) return 0;
	return 1;
}
int dfs(int u,int ans){
	if(u==t){
		return ans;
	}
	int d=ans;
	for(int i=c[u];i;i=nx[i]){
		int v=to[i],w=zhi[i];
		c[u]=i;
		if(w>0&&ceng[v]==ceng[u]+1){
			int p=dfs(v,min(w,d));
			d-=p;
			zhi[i]-=p;
			zhi[i^1]+=p;
		}
	}
	return ans-d;
}
int maxx;
void jian(int u,int v,int w){
	add(u,v,w);
	add(v,u,0);
} 
inline int read()
{
	register int x=0,f=1;register char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}
signed main(){
	n=read();
	num=n+1;
	s=0;
	t=n+1;
	int u,v,w;
	for(int i=1;i<=n;i++){
		int a;
		a=read();
		maxx+=a;
		jian(s,i,a);
	}	
	for(int i=1;i<=n;i++){
		int b;
		b=read();
		maxx+=b;
		jian(i,t,b);
	}
	
	m=read();
	for(int i=1;i<=m;i++){
		int k,c1,c2,p;
		int n1=++num,n2=++num; 
		k=read();
		c1=read();
		c2=read();
		maxx+=c1;
		maxx+=c2;
		for(int j=1;j<=k;j++){
			p=read();
			jian(n1,p,2147483647);
			jian(p,n2,2147483647);
		}
		jian(s,n1,c1);
		jian(n2,t,c2);
	}
	int c,ans=0;
	while(bfs(s)){
		c=dfs(s,2147483647);
		if(c==-1) break;
		ans+=c; 
	}
	printf("%lld",maxx-ans);
	return 0;
}
2020/12/4 09:20
加载中...