萌新刚学网络流, dinic TLE55分求助
查看原帖
萌新刚学网络流, dinic TLE55分求助
77106
甜菜根楼主2023/7/24 16:22
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int S,T,n,m,level[3010];
int hd[3000010],nxt[3000010],to[3000010],tot=1,c[3000010],f[3000010],cur[3000010];
inline void add(int x,int y,int z){
	to[++tot]=y;
	c[tot]=z;
	nxt[tot]=hd[x];
	hd[x]=tot;
}
void link(int x,int y,int z){
	add(x,y,z);
	add(y,x,0);
}
int dinic_dfs(int u,int cp){
	if(u==T){
		return cp;
	}
	int tmp=cp;
	for(int i=cur[u];i;i=nxt[i]){
		int v=to[i];
		if(level[u]+1==level[v]&&c[i]>f[i]){
			int t=dinic_dfs(v,min(tmp,c[i]-f[i]));
			f[i]+=t;
			f[i^1]-=t;
			tmp-=t;
			if(tmp==0){
				break;
			}
		}
	}
	return cp-tmp;
}
bool dinic_bfs(){
	memset(level,0,sizeof(level));
	level[S]=1;
	queue<int> q;
	q.push(S);
	while(!q.empty()){
		int u=q.front(); q.pop();
		if(u==T){
			return 1;
		}
		for(int i=hd[u];i;i=nxt[i]){
			int v=to[i];
			if(!level[v]&&c[i]>f[i]){
				level[v]=level[u]+1,q.push(v);
			}
		}
	}
	return 0;
}
int dinic(){
	int sum=0;
	while(dinic_bfs()){
		for(int i=1;i<=n;i++){
			cur[i]=hd[i];
		}
		sum+=dinic_dfs(S,inf);
	}
	return sum;
}
int ttt;
int main(){
	cin>>n;
	S=n+1;
	T=n+2;
	for(int i=1;i<=n;i++){
		int u;
		cin>>u;
		ttt+=u;
		link(S,i,u);
	}
	for(int i=1;i<=n;i++){
		int u;
		cin>>u;
		ttt+=u;
		link(i,T,u);
	}
	n=n+2;
	int m;
	cin>>m;
	int cc,ta,tb;
	int x;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&cc,&ta,&tb);
		ttt+=ta+tb;
		int lk=++n,rk;
		link(S,n,ta);
		rk=++n;
		link(n,T,tb);
		for(int j=0;j<cc;j++){
			scanf("%d",&cx);
			link(lk,x,inf);
			link(x,rk,inf);
		}
	}
	cout<<ttt-dinic();
	return 0;
}
2023/7/24 16:22
加载中...