网络流20分求调qwq
查看原帖
网络流20分求调qwq
956129
z_z_b_楼主2024/7/4 21:33

AC2,7,剩下的都T了awa

#include<bits/stdc++.h>
#define int long long
using namespace std;

namespace io
{
	inline int read(){int x=0,w=0;char c=0;while(!isdigit(c))w|=c=='-',c=getchar();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();return w?-x:x;}
	template<typename T>inline void write(T x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');}
	template<typename T>inline void write_(T x){write(x),putchar(' ');}
	template<typename T>inline void writeln(T x){write(x),putchar('\n');}
}
using namespace io;

const int N=3e5+10,M=3005;
int n,s,t,top=1,ans,cnt,d[M],now[M],nx[M],fl[M],h[N];
int mp[510],S,T;
bool v[M];
struct node{int nx,to,w,d;}e[N<<1];

void add(int u,int v,int w,int d)
{
	e[++top]=(node){h[u],v,w,d},h[u]=top;
	e[++top]=(node){h[v],u,0,-d},h[v]=top;
}

bool bfs()
{
	memset(d,0x7f,sizeof d);
	memset(fl,0x7f,sizeof fl);
	memset(v,0,sizeof v);
	queue<int> q;
	q.push(S);
	v[S]=1,d[S]=0,now[T]=-1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		v[u]=0;
		for(int i=h[u];i;i=e[i].nx)
		{
			int w=e[i].w,k=e[i].d,to=e[i].to;
			if(e[i].w>0&&d[to]>d[u]+k)
			{
				d[to]=d[u]+k,now[to]=u;
				nx[to]=i,fl[to]=min(fl[u],w);
				if(!v[to]) v[to]=1,q.push(e[i].to);
			}
		}
	}
	return now[T]!=-1;
}

void dfs(int k)
{
	ans+=fl[k]*d[k];
	while(k!=s)
	{
		e[nx[k]].w-=fl[t];
		e[nx[k]^1].w+=fl[t];
		k=now[k];
	}
}

signed main()
{
	n=read();
	s=1,t=n+1;
	S=t+1,T=S+1;
	for(int i=1;i<=n;i++)
	{
		int t=read();
		for(int j=1;j<=t;j++)
		{
			int v=read(),w=read();
			++d[v],--d[i];
			ans+=w;
			add(i,v,INT_MAX,w);
		}
	}
	for(int i=2;i<=n;i++) add(i,t,INT_MAX,0);
	add(t,s,INT_MAX,0);
	for(int i=1;i<=n+1;i++)
	{
		if(d[i]>0) add(S,i,d[i],0);
		if(d[i]<0) add(i,T,-d[i],0);
	}
	while(bfs()) dfs(T);
	write(ans);
	return 0;
}
2024/7/4 21:33
加载中...