题目描述
有\(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\)
\[\begin{align}
\frac{B}{A}&>s\\
B&>As\\
B-As&>0
\end{align}
\]
\frac{B}{A}&>s\\
B&>As\\
B-As&>0
\end{align}
\]
问题转化成买一个物品获得\(-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;
}