发传单

C++14(g++5.4) 解法, 执行用时: 193ms, 内存消耗: 5216K, 提交时间: 2019-09-17 19:49:24

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int N=1e5+10;
const int M=1e6+10;
const int mx=2e6;
struct MCMF{
	int h[N],ne[M],to[M],flow[M],w[M],tot,dis[N],liu[N],pre[N],inq[N],s,t;
	int ans;
	void init(int a,int b){
		s=a;t=b;
		for(int i=0;i<M;i++)ne[i]=0;
		for(int i=0;i<N;i++)h[i]=0;
		tot=1;ans=0;
	}
	void addedge(int x,int y,int z,int c){
		to[++tot]=y;ne[tot]=h[x],h[x]=tot,flow[tot]=z;w[tot]=c;
		swap(x,y);
		to[++tot]=y;ne[tot]=h[x],h[x]=tot,flow[tot]=0;w[tot]=-c;
	}
	int bfs(){
		for(int i=0;i<=t;i++)dis[i]=inf,liu[i]=inf,inq[i]=pre[i]=0;
		queue<int>q;int x;dis[s]=0;q.push(s);
		while(!q.empty()){
			x=q.front();q.pop();inq[x]=0;
			for(int i=h[x];i;i=ne[i]){
				int v=to[i];
				if(flow[i]>0&&dis[x]+w[i]<dis[v]){
					dis[v]=dis[x]+w[i],pre[v]=i;
					liu[v]=min(liu[x],flow[i]);
					if(!inq[v])inq[v]=1,q.push(v);
				}
			}
		}
		if(!pre[t])return 0;
		x=t;ans+=dis[t]*liu[t];
		while(x!=s){
			int kl=pre[x];
			flow[kl]-=liu[t];flow[kl^1]+=liu[t];x=to[kl^1];
		}
		return 1;
	}
	int mcmf(){
		while(bfs()){}
		return ans;
	}
}F;
int d[N];
void add(int u,int v,int down,int up,int w){
	F.addedge(u,v,up-down,w);
	d[u]-=down,d[v]+=down;
}
int n,s,t,S,T;
int main()
{
	scanf("%d",&n);s=2*n+1;t=2*n+2;S=2*n+3,T=2*n+4;
	F.init(S,T);add(t,s,0,inf,0);
	for(int i=1,x;i<=n;i++){
		scanf("%d",&x);
		add(s,i,0,inf,x+mx);
	}
	for(int i=1;i<=n;i++){
		int tt,x,y;
		add(i,i+n,1,inf,0);
		add(i+n,t,0,inf,0);
		scanf("%d",&tt);
		while(tt--){
			scanf("%d%d",&x,&y);
			add(i+n,x,0,inf,y);
		}
	}
	for(int i=1;i<=t;i++)if(d[i]>0)F.addedge(S,i,d[i],0);else if(d[i]<0)F.addedge(i,T,-d[i],0);
	cout<<F.mcmf()%mx<<endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 195ms, 内存消耗: 1204K, 提交时间: 2020-10-08 12:17:53

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=4e5+10;
const int inf=1e9;
int a[maxn];
int n,m,vis[maxn],s,t,ss,tt,in[maxn],dis[maxn],pre[maxn],flow[maxn];
struct edge{
	int to,nxt,flow,w;
}d[maxn]; int head[maxn],cnt=1,ans;
void add(int u,int v,int flow,int w)
{
	d[++cnt]=(edge){v,head[u],flow,w},head[u]=cnt;
	d[++cnt]=(edge){u,head[v],0,-w},head[v]=cnt;
}
void ins(int u,int v,int l,int r,int w)
{
	add(u,v,r-l,w);
	in[u]-=l,in[v]+=l,ans+=l*w;
}
bool spfa(int s,int t)
{
	for(int i=0;i<=tt;i++)	dis[i]=1e18;
	queue<int>q; q.push(s);
	dis[s]=0, flow[s]=inf;
	while( !q.empty() )
	{
		int u=q.front(); q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=d[i].nxt )
		{
			int v=d[i].to;
			if( dis[v]>dis[u]+d[i].w&&d[i].flow )
			{
				dis[v] = dis[u]+d[i].w;
				pre[v]=i;
				flow[v]=min( flow[u],d[i].flow );
				if( !vis[v] )	vis[v]=1,q.push(v);
			}
		}
	}
	return (dis[t]!=1e18);
}
int dinic(int s,int t)
{
	int ans=0,x,i;
	while( spfa(s,t) )
	{
		ans+=flow[t]*dis[t];
		x=t;
		while( x!=s )
		{
			i = pre[x];
			d[i].flow-=flow[t],d[i^1].flow+=flow[t];
			x = d[i^1].to;
		}
	}
	return ans;
}
signed main()
{
	cin >> n;
	s=0,t=n+n+1;
	for(int i=1;i<=n;i++)	cin >> a[i];
	for(int i=1;i<=n;i++)
	{
		ins(s,i,0,inf,a[i]+inf);
		ins(i+n,t,0,inf,0);
		ins(i,i+n,1,inf,0);
		int k; cin >> k;
		while( k-- )
		{
			int v,w; cin >> v >> w;
			ins(i+n,v,0,inf,w);
		}
	}
	ss=t+1,tt=ss+1;
	for(int i=s;i<=t;i++)
	{
		if( in[i]>0 )	add(ss,i,in[i],0);
		else	add(i,tt,-in[i],0);
	}
	add(t,s,inf,0);
	cout << ( ans+dinic(ss,tt) )%inf;
}

详情