题解 P2868 【[USACO07DEC]观光奶牛Sightseeing Cows】

· · 题解

提供一个暴力算法。

我们今天考了这道题目，然后我一看这东西一副不可做的样子。然后就用30min打了一个暴力，结果有80？

于是我又加上一些玄学的STL的优化过掉了考试的数据，在洛谷上开O2也可以卡过去。

思路： 显而易见我们可以枚举每一个点，然后以它为起点跑最短路，找到一个单位时间快乐值最大的环，其可以更新最优解的条件显然是当前到这个点最优的路径的单位时间乐趣值小于本条路径的单位时间乐趣值。

至于为什么自己想想。。。

实际上这道题目的难点只是在于怎样判断一个点经过两次的情况。那么我们可以定义一个结构体：

struct node{
    int u;//当前节点的编号
    bool used[N];//编号为 i 的点是否经过了一次
    void init(int x)
    {
        u=x;
        memset(used,false,sizeof(used));
    }
}st;

这样我们就可以在跑最短路的时候往队列里丢这个结构体类型的变量就可以了。

附上考场代码：

void bfs(int s)
{
    memset(Fsum,0,sizeof(Fsum));
    memset(Tsum,0,sizeof(Tsum));
    memset(vis,false,sizeof(vis));
    Fsum[s]=F[s];
    st.init(s);
    st.used[s]=true;
    q.push(st),vis[s]=true;
    while(!q.empty())
    {
        node qq=q.front();
        int u=qq.u;
        q.pop(),vis[u]=false;
        for(int e=head[u];e;e=r[e].next)
        {
            int v=r[e].to,w=r[e].w;
            if(Fsum[v]==0||Tsum[v]==0)//如果还没有走到这里
            {
                node c=qq;
                c.u=v;
                Fsum[v]=Fsum[u];
                if(!c.used[v])Fsum[v]+=F[v],c.used[v]=true;
                Tsum[v]=Tsum[u]+w,q.push(c);
                vis[v]=true;
            }
            else
            {
                double x=Fsum[v]/Tsum[v],y;
                node c=qq;
                int fs=Fsum[u],ts=Tsum[u]+w;
                if(!c.used[v])fs+=F[v];
                y=fs/ts;
                if(x<y)//走到过这里但是当前解更优
                {
                    c.used[v]=true;
                    c.u=v;
                    Fsum[v]=fs,Tsum[v]=ts;
                    if(!vis[v])q.push(c);
                }
            }
        }
    }
}//被卡了精度多WA了一个点TAT

但是这样的算法时间复杂度很高，尤其在结构体的预处理和状态继承的时候。

于是我们想到，STL里有个叫做bitset的东西：

bitset<N> b[N];

这个东西表示一个 N 位的二进制数，相当于一个二维的布偶型数组，但有一个不一样的地方，它支持这样的操作：

b[v]=b[u];

于是它就可以跑得飞快

然后代码写出来就成了这样：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<bitset>
using namespace std;

const int N = 1000 + 10;
const int M = 5000 + 10;

inline int read()
{
    int res=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+ch-'0';ch=getchar();}
    return res;
}

int n,m;

struct edge{
    int next,to,w;
}r[M];

int head[N],tot;

void add(int u,int v,int w)
{
    tot++;
    r[tot].next=head[u];
    head[u]=tot;
    r[tot].to=v;
    r[tot].w=w;
}

int F[N],Fsum[N],Tsum[N];

bool vis[N];

bitset<N> b[N];

queue<int> q;

void bfs(int s)
{
    for(int i=1;i<=n;i++)
        b[i]=Fsum[i]=Tsum[i]=0,vis[i]=false;
    Fsum[s]=F[s];
    q.push(s),vis[s]=true;
    b[s][s]=1;
    while(!q.empty())
    {
        int u=q.front();
        for(int e=head[u];e;e=r[e].next)
        {
            int v=r[e].to,w=r[e].w,fs=Fsum[u]+(!b[u][v]?F[v]:0),ts=Tsum[u]+w;
            double x=Fsum[v]*1.0/Tsum[v],y=fs*1.0/ts;
            if(!Tsum[v]||x<y)
            {
                Fsum[v]=fs;
                b[v]=b[u],b[v][v]=1;
                Tsum[v]=ts;
                if(!vis[v])q.push(v),vis[v]=true;
            }
        }
        q.pop(),vis[u]=false;
    }
}

double ans;

int main()
{
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        F[i]=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read(),w=read();
        add(u,v,w);
    }
    for(int i=1;i<=n;i++)
    {
        bfs(i);
        if(Tsum[i]!=0)ans=max(ans,Fsum[i]*1.0/Tsum[i]);
//      cout<<Fsum[i]<<" "<<Tsum[i]<<endl;
    }
    printf("%.2f\n",ans);
    return 0;
}

但毕竟是个暴力，在洛谷上只能吸氧过了，我好菜啊qwq