题目描述

　　有\(n\)个物品，买第\(i\)个物品要花费\(a_i\)元。还有\(m\)对关系：同时买\(p_i,q_i\)两个物品会获得\(b_i\)点收益。

　　设收益为\(B\)，花费为\(A\)，求\(\lceil\frac{B}{A}\rceil-1\)

　　\(n\leq 400,m\leq 200000,1\leq a_i,b_i\leq 100\)

题解

　　显然这是一个分数规划问题。

　　二分答案\(s\)，判断答案是否能大于\(s\)

　　问题转化成买一个物品获得\(-a_is\)点收益，求收益是否能\(>0\)

　　显然这个可以用最大权闭合子图来做，点数为\(n+m+2\)，边数为\(n+3m\)，肯定会TLE

　　考虑另一种连边方法。

　　对于每个点\(i\)，连边\((S,i,-a_is)\)

　　对于每一对关系，列一个方程，解得：连边\((p_i,q_i,\frac{1}{2}b_i),(q_i,p_i,\frac{1}{2}b_i),(p_i,T,\frac{1}{2}b_i),(q_i,T,\frac{1}{2}b_i)\)。

　　答案就是\(\sum_{i=1}^mb_i-maxflow\)

　　因为容量为分数不好处理，所以可以把全部数\(\times 2\)。

　　这样做的点数是\(n+2\)，边数是\(2n+m\)。

　　写ISAP不用卡常美滋滋。

代码

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

typedef long long ll;

int rd()

{

	int s=0,c;

	while((c=getchar())<'0'||c>'9');

	s=c-'0';

	while((c=getchar())>='0'&&c<='9')

		s=s*10+c-'0';

	return s;

}

int sum=0;

namespace flow

{

	int c[10000010];

	int v[10000010];

	int t[10000010];

	int h[4010];

	int n;

	void add(int x,int y,int a)

	{

		n++;

		v[n]=y;

		c[n]=a;

		t[n]=h[x];

		h[x]=n;

	}

	void init()

	{

		memset(h,0,sizeof h);

		n=0;

	}

	int S,T;

	int num;

	int d[4010];

	int e[4010];

	int cur[4010];

	int op(int x)

	{

		return ((x-1)^1)+1;

	}

	queue<int> q;

	void bfs()

	{

		memset(d,-1,sizeof d);

		memset(e,0,sizeof e);

		d[T]=0;

		q.push(T);

		int x,i;

		while(!q.empty())

		{

			x=q.front();

			q.pop();

			e[d[x]]++;

			for(i=h[x];i;i=t[i])

				if(c[op(i)]&&d[v[i]]==-1)

				{

					d[v[i]]=d[x]+1;

					q.push(v[i]);

				}

		}

	}

	int dfs(int x,int flow)

	{

		if(x==T)

			return flow;

		int s=0,u;

		for(int &i=cur[x];i;i=t[i])

			if(d[v[i]]==d[x]-1&&c[i])

			{

				u=dfs(v[i],min(flow,c[i]));

				s+=u;

				flow-=u;

				c[i]-=u;

				c[op(i)]+=u;

				if(!flow)

					return s;

			}

		e[d[x]]--;

		if(!e[d[x]])

			d[S]=num;

		e[++d[x]]++;

		cur[x]=h[x];

		return s;

	}

	int solve()

	{

		bfs();

		memcpy(cur,h,sizeof h);

		int ans=0;

		while(ans<2*sum&&d[S]>=0&&d[S]<=num-1)

			ans+=dfs(S,2*sum-ans);

		return ans;

	}

}

using flow::S;

using flow::T;

using flow::num;

int n,m;

int lx[2000010];

int ly[2000010];

int lz[2000010];

int s[4010];

int a[4010];

void add(int x,int y,int z)

{

	flow::add(x,y,z);

	flow::add(y,x,0);

}

void add2(int x,int y,int z)

{

	flow::add(x,y,z);

	flow::add(y,x,z);

}

int check(int x)

{

	flow::init();

	int i;

	S=n+1;

	num=T=n+2;

	for(i=1;i<=n;i++)

	{

		add(S,i,int(min(0x7fffffffll,2ll*a[i]*x)));

		add(i,T,s[i]);

	}

	for(i=1;i<=m;i++)

		if(lx[i]!=ly[i])

			add2(lx[i],ly[i],lz[i]);

	return flow::solve()<2*sum;

}

int main()

{

#ifndef ONLINE_JUDGE

	freopen("c.in","r",stdin);

	freopen("c.out","w",stdout);

#endif

//	scanf("%d%d",&n,&m);

	n=rd();

	m=rd();

	int i;

	for(i=1;i<=n;i++)

//		scanf("%d",&a[i]);

		a[i]=rd();

	for(i=1;i<=m;i++)

	{

//		scanf("%d%d%d",&lx[i],&ly[i],&lz[i]);

		lx[i]=rd();

		ly[i]=rd();

		lz[i]=rd();

		s[lx[i]]+=lz[i];

		s[ly[i]]+=lz[i];

		sum+=lz[i];

	}

	int l=0,r=sum;

	while(l<r)

	{

		int mid=(l+r+1)>>1;

		if(check(mid))

			l=mid;

		else

			r=mid-1;

	}

	printf("%d\n",l);

	return 0;

}