Dinic被TLE,求哪写挂了
查看原帖
Dinic被TLE,求哪写挂了
363495
我爱杨帆楼主2021/2/5 11:34
#include<bits/stdc++.h>
#define int long long 
#define re register
#define inf 1e18
const int sz=2e6+5;
using namespace std;
int read()
{
	char c=getchar();
	int r=0,f=1;
	while((c<'0'||c>'9')&&c!='-')
		c=getchar();
	if(c=='-') {
		f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		r=r*10+c-'0';
		c=getchar();
	}
	return f*r;
}
struct node
{
	int to,nxt,c;
}e[sz];
int tot=1,head[sz],now[sz];
void add_edge(int u,int v,int z)
{
	e[++tot]=(node){v,head[u],z};head[u]=tot;
	e[++tot]=(node){u,head[v],0};head[v]=tot;
}
int dep[sz];
bool bfs(int s,int t)
{
	memset(dep,0,sizeof(dep));
	queue<int >q;
	dep[s]=1;now[s]=head[s];
	q.push(s);
	while(q.size())
	{
		int top=q.front();q.pop();
		for(int i=head[top];i;i=e[i].nxt)
			if(!dep[e[i].to]&&e[i].c)
			{
				q.push(e[i].to);
				now[e[i].to]=head[e[i].to];
				dep[e[i].to]=dep[top]+1;
				if(e[i].to==t) return 1;
			}
	}
	return 0;
}
int dfs(int x,int flow,int t)
{
	if(x==t||!flow) return flow;
	int rest=flow;
	for(int &i=now[x];i;i=e[i].nxt)
	{
		now[x]=i;
		if(e[i].c&&dep[e[i].to]==dep[x]+1)
		{
			int k=dfs(e[i].to,min(rest,e[i].c),t);
			if(!k)
			{
				dep[e[i].to]=0;
				continue;
			}
			e[i].c-=k;
			e[i^1].c+=k;
			rest-=k;
		}
	}
	return flow-rest;
}
int dinic(int s,int t)
{
	int maxflow=0,flow=0;
	while(bfs(s,t))
		while(flow=dfs(s,inf,t)) maxflow+=flow;
	return maxflow;
}
int sum,a[sz],b[sz];
signed main()
{
	int n=read();
	for(int i=1;i<=n;i++) a[i]=read(),sum+=a[i];
	for(int i=1;i<=n;i++) b[i]=read(),sum+=b[i];
	int m=read();
	int s=0,t=m*2+n+1;
	for(int i=1;i<=n;i++) add_edge(s,i,a[i]);
	for(int i=1;i<=n;i++) add_edge(i,t,b[i]);
	for(int i=1;i<=m;i++)
	{
		int k=read();
		int c1=read(),c2=read();
		sum+=c1;sum+=c2;
		add_edge(s,n+i*2-1,c1);
		add_edge(n+i*2,t,c2);
		for(int j=1;j<=k;j++)
		{
			int x=read();
			add_edge(n+i*2-1,x,inf);
			add_edge(x,n+i*2,inf);
		}
	}
	cout<<sum-dinic(s,t)<<endl;
//	cout<<sum<<endl;
	
}
/*
3
4 2 1
2 3 2
1
2 3 2 1 2 */

2021/2/5 11:34
加载中...