Luogu

LOJ

分析

考虑到背包的大小只有 $1$ ,那么在环上走时一定是 买-卖-买-卖-…

可以考虑预处理出 $dis[i][j]$ ,表示 $i$ 到 $j$ 的距离;再预处理出 $w[i][j]$ ,表示 $i$ 买 $j$ 卖的最大收益。

发现题目要求一个最小的 $x$ 满足 $\displaystyle\frac{\sum w}{\sum dis}\leq x$ 。这个式子长的非常 $0/1$ 分数规划。

二分答案 $mid$ ,那么就相当于 $\displaystyle\sum(w-mid\cdot dis)\leq 0$ 。

对于每个点对 $(u,v)$ 建一条边,边权为 $w[u][v]-mid\cdot dis[u][v]$ ,然后 SPFA 判负环即可。

另外这题很恶心地卡了精度...我交了一页才过...

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
#define double long double
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100+10,M=10000+10,K=1000+10;
const int inf=0x3f3f3f3f;
const double eps=1e-9;

int n,m,k;

struct edge { int v,nxt; double w; } e[M];
int head[N],e_cnt=0;

inline void addEdge(int u,int v,double w) {
    e[++e_cnt]=(edge){v,head[u],w},head[u]=e_cnt;
}

int b[N][K],s[N][K];
int dis[N][N],w[N][N];

double d[N]; int inq[N],cnt[N];

inline int check(double mid) {
    queue<int> Q;
    memset(head,0,sizeof(head)),e_cnt=0;
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=n;++j)
            if (i!=j&&dis[i][j]!=inf)
                addEdge(i,j,dis[i][j]*mid-w[i][j]);
    for (re int i=1;i<=n;++i) d[i]=0,inq[i]=cnt[i]=1;
    for (re int i=1;i<=n;++i) Q.push(i);
    while (!Q.empty()) {
        int u=Q.front(); inq[u]=0,Q.pop();
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v; double w=e[i].w;
            if (d[u]+w<d[v]) {
                d[v]=d[u]+w,cnt[v]=cnt[u]+1;
                if (cnt[v]>n) return 0;
                if (!inq[v]) inq[v]=1,Q.push(v);
            }
        }
    }
    return 1;
}

int main() {
    n=read(),m=read(),k=read();
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=k;++j)
            b[i][j]=read(),s[i][j]=read();
    memset(dis,0x3f,sizeof(dis));
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read(),w=read();
        dis[u][v]=w;
    }
    for (re int i=1;i<=n;++i) dis[i][i]=0;
    for (re int k=1;k<=n;++k)
        for (re int i=1;i<=n;++i)
            for (re int j=1;j<=n;++j)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    for (re int u=1;u<=n;++u)
        for (re int v=1;v<=n;++v)
            for (re int i=1;i<=k;++i)
                if (b[u][i]!=-1&&s[v][i]!=-1)
                    w[u][v]=max(w[u][v],s[v][i]-b[u][i]);
    double L=0,R=1e9;
    while (R-L>eps) {
        double mid=(L+R)/2;
        if (check(mid)) R=mid;
        else L=mid;
    }
    printf("%d\n",(int)R);
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 13 PM