学步园

我用的二分边长+网络流,这题也可以用枚举边长+并查集来做

对于每个有金矿的点,源点向其连一条容量为金矿数的边,对于每个仓库,向汇点连一条容量为仓库储存量的边,然后对于所有边长不大于当前枚举的值的边,连双向的容量为无穷的边

如果满流,则该枚举的边长可行,继续缩小,否则,枚举更大的边长

边长去重写错了,wa了几次=.=

代码:

#include<iostream>
#include<memory.h>
#include<string>
#include<cstdio>
#include<algorithm>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<ctime>
using namespace std;
const int MAX=1005;
const int inf=1<<30;
struct node 
{
	int v,c,next;
}g[MAX*100];
struct Edge 
{
	int u,v,w;
}E[MAX*MAX];
int adj[MAX],num[MAX],pre[MAX],cur[MAX],dis[MAX],e,n,m,vn,s,t;
int pos[MAX*MAX],mine[MAX],store[MAX],sum,tot;
void add(int u,int v,int c)
{
	g[e].v=v; g[e].c=c; g[e].next=adj[u]; adj[u]=e++;
	g[e].v=u; g[e].c=0; g[e].next=adj[v]; adj[v]=e++;
	//cout<<u<<" "<<v<<" "<<c<<endl;
}
int sap()
{
	int i,u,v,flag,flow=0,aug=inf;
	for(i=0;i<=vn;i++)
	{
		cur[i]=adj[i];
		dis[i]=num[i]=0;
	}
	num[0]=vn; 
	pre[s]=u=s;
	while(dis[s]<vn)
	{
		flag=0;
		for(i=cur[u];i!=-1;i=g[i].next)
		{
			v=g[i].v;
			if(g[i].c&&dis[u]==dis[v]+1)
			{
				flag=1;
				cur[u]=i;
				pre[v]=u;
				aug=min(aug,g[i].c);
				u=v;
				if(u==t)
				{
					flow+=aug;
					while(u!=s)
					{
						u=pre[u];
						g[cur[u]].c-=aug;
						g[cur[u]^1].c+=aug;
					}
					aug=inf;
				}
				break;
			}
		}
		if(flag)
			continue;
		if(--num[dis[u]]==0)
			break;
		for(dis[u]=vn,i=adj[u];i!=-1;i=g[i].next)
		{
			v=g[i].v;
			if(g[i].c&&dis[v]<dis[u])
			{
				cur[u]=i; dis[u]=dis[v];
			}
		}
		dis[u]++;
		num[dis[u]]++;
		u=pre[u];
	}
	return flow;
}
bool check(int x)
{
	int i;
	memset(adj,-1,sizeof(adj));
	e=0; s=0; t=n+1; vn=t+1;
	for(i=1;i<=n;i++)
	{
		if(mine[i])
			add(s,i,mine[i]);
		if(store[i])
			add(i,t,store[i]);
	}
	for(i=0;i<m;i++)
	{
		if(E[i].w<=x)
		{
			add(E[i].u,E[i].v,inf);
			add(E[i].v,E[i].u,inf);
		}
	}
	return sap()==sum;
}
void solve(int r)
{
	int i,l=0,mid,ans=-1;
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(check(pos[mid]))
		{
			ans=pos[mid];
			r=mid-1;
		}
		else
			l=mid+1;
	}
	if(ans==-1)
		puts("No Solution");
	else
		printf("%d\n",ans);
}
int main()
{
	int i,j,k;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)
			break;
		sum=0;
		tot=0;
		for(i=1;i<=n;i++)
		{
			scanf("%d",&mine[i]);
			sum+=mine[i];
		}
		for(i=1;i<=n;i++)
		{
			scanf("%d",&store[i]);
			tot+=store[i];
		}
		scanf("%d",&m);
		j=0;
		for(i=0;i<m;i++)
		{
			scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w);
			pos[j++]=E[i].w;
		}
		//pos[j++]=0;
		if(tot<sum)
		{
			puts("No Solution");
			continue;
		}
		sort(pos,pos+j);
		k=0;
		for(i=0;i<j;i++)
		{
			if(i==0||pos[i]!=pos[i-1])
				pos[k++]=pos[i];
		}
		solve(k);
	}
	return 0;
}