求调
查看原帖
求调
800499
suzhikz楼主2024/6/13 23:18
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<queue>
#include<vector>
#include<stdio.h>
#include<map>
#include<set>
#include<string.h>
#include<time.h>
#include<stdlib.h>
#include<bitset>
using namespace std;
const long long inf=0x3f3f3f3f;
const int N=3e3+5,M=8e3+5;
int n,m;
int head[N],to[M],nex[M],cnt=1;
long long w[M];
void add(int u,int v,int ww){
	cnt++;
	to[cnt]=v;
	nex[cnt]=head[u];
	w[cnt]=ww;
	head[u]=cnt;
}
void ad(int u,int v,int ww){
	add(u,v,ww);add(v,u,0);
}
int s,t;
long long summ,ans;
long long d[N],noww[N];
bool bfs(){
	queue<int>q;
	for(int i=1;i<N;i++)d[i]=inf;
	q.push(s);
	d[s]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		noww[u]=head[u];
		for(int i=head[i];i;i=nex[i]){
			int v=to[i];
			if(d[v]!=inf)continue;
			if(w[i]==0)continue;
			d[v]=d[u]+1;
			q.push(v);
		}
	}
	return d[t]!=inf;
}
long long dfs(int u,long long summ){
	if(u==t)return summ;
	long long tmp,us=0;
	for(int i=noww[u];i;i=nex[i]){
		noww[u]=i;
		int v=to[i];
		if(w[i]==0)continue;
		if(d[v]!=d[u]+1)continue;
		tmp=dfs(v,min(summ,w[i]));
		if(tmp==0)d[v]=inf;
		us+=tmp;
		w[i]-=tmp;
		w[i^1]+=tmp;
		summ-=tmp;
		if(!summ)break;
	}
	return us;
}
int main(){
	cin>>n;s=0,t=N-3;
	for(int i=1,u;i<=n;i++){
		cin>>u;
		summ+=u;
		ad(0,i,u);
	}
	for(int i=1,u;i<=n;i++){
		cin>>u;summ+=u;
		ad(i,t,u);
	}
	cin>>m;
	for(int i=1,w1,w2,op,u;i<=m;i++){
		cin>>op>>w1>>w2;summ+=w1+w2;
		ad(0,n+1,w1);ad(n+2,t,w2);
		for(int j=1;i<=op;i++){
			cin>>u;
			ad(n+1,u,inf);
			ad(u,n+2,inf);
		}
		n+=2;
	}
	while(bfs()){
		ans+=dfs(s,inf);
		//cout<<ans<<endl;
	}
	cout<<summ-ans;
	return 0;
}

2024/6/13 23:18
加载中...