网络流模板求调
查看原帖
网络流模板求调
763878
Jerry_heng楼主2024/4/4 20:53

死循环了

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mxn=1e4+10;
const int inf=1e8,s=0,t=100000;
int cnt=1,m,cntt,dep[mxn],n,k,c1,c2,cur[mxn],sum,a[mxn],b[mxn],head[mxn];
struct node{
	int to,nxt,val;
}edge[mxn<<3];
void add(int u,int v,int w){
	edge[++cnt]=(node){v,head[u],w};
	head[u]=cnt;
	edge[++cnt]=(node){u,head[v],0};
	head[v]=cnt;
}
bool bfs(){
	memset(dep,0,sizeof dep);
	memcpy(cur,head,sizeof head);
	queue<int>q;
	q.push(s);
	dep[s]=1;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=head[u];i;i=edge[i].nxt){
			int v=edge[i].to;
			if(dep[v]||!edge[i].val)continue;
			dep[v]=dep[u]+1;
			q.push(v);
		}
	}
	return dep[t];
}
int dfs(int u,int fl){
	if(u==t)return fl;
	int flow=0;
	for(int i=cur[u];i&&fl;i=edge[i].nxt){
		cur[u]=i;
		int v=edge[i].to;
		if(dep[v]!=dep[u]+1||!edge[i].val)continue;
		int c=dfs(v,min(fl,edge[i].val));
		fl-=c,flow+=c;
		edge[i].val-=c,edge[i^1].val+=c;
	}
	return flow;
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		add(s,i,a[i]);
		sum+=a[i];
	}
	for(int i=1;i<=n;i++){
		scanf("%lld",&b[i]);
		add(i,t,b[i]);
		sum+=b[i];
	}
	int tot=n;
	scanf("%lld",&m);
	while(m--){
		scanf("%lld%lld%lld",&k,&c1,&c2);
		add(s,tot+1,c1),add(tot+2,t,c2);
		sum+=c1+c2;
		for(int i=1;i<=k;i++){
			int u;
			scanf("%lld",&u);
			add(tot+1,u,inf),add(u,tot+2,inf);
		}
		tot+=2;
	}
	while(bfs()){
		sum-=dfs(s,inf);
		return 0;
	}
	printf("%lld\n",sum);
	return 0;
}
2024/4/4 20:53
加载中...