渐渐's Blog

题目大意：有N个站点，每个站点供应油的价格为Pi，有M条路，每条路耗油量为Ci。现在又Q个询问，求出，当坦克在S点，油量为0，要到达T点，油箱容量为V的最小价格。

分析：有点像dij，用一个数组used[ i ][ j ]记录，第i个站点，油量为j的情况是否出现过。用优先队列每次选出花费最小的节点更新。入队有2种情况：

1.当可以走向下一个节点时

2.当可以再买1升汽油时（保证每种情况都考虑到，DP的思想）

PS：代码写烂了...好慢

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
using namespace std;
#define MAXE 20020
#define MAXN 1010
#define SET(a,b) memset(a,b,sizeof(a))

int next[MAXE],p[MAXE],c[MAXE],st[MAXN],e;
int used[MAXN][110],price[MAXN];

void add(int a,int b,int d)
{
    next[e]=st[a];
    p[e]=b;
    c[e]=d;
    st[a]=e++;
}

struct Node
{
    int num,fuel,cost;
    Node(int num,int fuel,int cost):num(num),fuel(fuel),cost(cost){}
    friend bool operator < (Node a,Node b)
    {
        return a.cost>b.cost;
    }
};


int work(int S,int T,int C)
{
    priority_queue<Node> Q;
    SET(used,0);
    Q.push(Node(S,0,0));
    used[S][0]=1;
    while(!Q.empty())
    {
        int u=Q.top().num,f=Q.top().fuel,m=Q.top().cost;
        if(u==T)return m;
        Q.pop();
        for(int v=st[u];v!=-1;v=next[v])
        {
            if(f>=c[v])
            {
                if(!used[p[v]][f-c[v]])
                {
                    used[p[v]][f-c[v]]=1;
                    Q.push(Node(p[v],f-c[v],m));
                }
            }
        }
        if(f+1<=C&&!used[u][f+1])Q.push(Node(u,f+1,m+price[u]));
    }
    return -1;
}

int main()
{
    int N,M;
    SET(st,-1);e=0;
    scanf("%d%d",&N,&M);
    int i,j,k;
    for(i=1;i<=N;i++)scanf("%d",price+i);
    for(i=1;i<=M;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        x++,y++;
        add(x,y,z);
        add(y,x,z);
    }
    int P;
    scanf("%d",&P);
    for(i=1;i<=P;i++)
    {
        int S,T,C;
        scanf("%d%d%d",&C,&S,&T);
        S++,T++;
        int tttt=work(S,T,C);
        if(tttt==-1)printf("impossible\n");
        else printf("%d\n",tttt);
    }
    //system("pause");
    return 0;
}
    
                    

题目大意：有一个单向图，可以从任意一点出发，回到该点，每条路都会耗费一定的时间ti。每到一个新的点都会得到一定的分数fi。求一条路使得∑fi/∑ti最大。

题目分析：我们设最优解经过的城市为环 n1->n2->...nk->n1，我们可以猜测最优解的路上不会重复经过一个点(除去出发点)。简略证明：

    假设一个非出发点k被重复经过了，那么k点至少连接了两个环。我们设第一个环的解为:x1 = F1/T1 ，第二个环的解为:x2 = F2/T2。总的解为: x3 = (F1+F2-fk)/(T1+T2)<max(x1,x2)。

    那么最优解为 x' = (fn1+fn2+.....fnk)/(e(n1,n2),e(n2,n3)+....e(nk,n1))。 x' = F/T -> T * x' - F = 0。

    为了求解出这个最优值x'，我们设函数 g(x)=T*x-F。这是一个单调函数。所以可以用二分求出答案。

/*

简略证明：

我们设T(y),F(y)为函数（当y不同，表示选取不同的环），设x1<x2，y1 为使 g(x1) 取得最小值的解选择，则：

g(x1) = max(T(y) * x1 - F(y))  = T(y1) * x1 - F(y1) < T(y1)*x2 - F(y1) <=max( T(y)*x2 - F(y) ) = g(x2)

*/

当g(x)>0时，x > x'

当g(x)<0时，x < x'

当g(x)=0时，x = x'

我们可以改变所有边权为 : t*x-f，用spfa求解是否存在负环（g(x)<0），存在增大x，否则减小x

我们把所有没松弛过的点，当成源点，spfa一次...但这题似乎直接对1点松弛也过了，是数据问题？？

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 1010
#define MAXE 5050
#define inf 1000000000.0
#define SET(a,b) memset(a,b,sizeof(a))
#define EPS 1e-3

int next[MAXE],p[MAXE],st[MAXN],e;
double dis[MAXN],f[MAXN],c[MAXE];
int used[MAXN],cnt[MAXN];

void add(int a,int b,double d)
{
    next[e]=st[a];
    p[e]=b;
    c[e]=d;
    st[a]=e++;
}

bool spfa(double mid,int S,int N)
{
    int i,j,k;
    queue<int> Q;
    for(i=1;i<=N;i++){
        dis[i]=inf;
        used[i]=0;
    }
    dis[S]=0.0;Q.push(S);
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        used[u]=0;
        for(int v=st[u];v!=-1;v=next[v])
        {
            double w=c[v]*mid-f[p[v]];
            if(dis[p[v]]-dis[u]-w>-EPS)
            {
                dis[p[v]]=dis[u]+w;
                if(!used[p[v]])
                {
                    used[p[v]]=1;
                    cnt[p[v]]++;
                    if(cnt[p[v]]>N)return true;
                    Q.push(p[v]);
                }
            }
        }
    }
    return false;
}

int main()
{
    SET(st,-1);e=0;
    int N,M;
    scanf("%d%d",&N,&M);
    int i,j,k;
    double l=0,r=0;
    for(i=1;i<=N;i++)
    {
        scanf("%lf",f+i);
        r+=f[i];
    }
    for(i=1;i<=M;i++)
    {
        int x,y;
        double z;
        scanf("%d%d%lf",&x,&y,&z);
        add(x,y,z);
    }
    while(r-l>EPS)
    {
        double mid=(l+r)/2;
        SET(cnt,0);
        bool flag=false;
        for(i=1;i<=N;i++)
            if(!cnt[i])
            {
                flag=spfa(mid,i,N);
                if(flag)break;
            }
        if(flag)l=mid;
        else r=mid;
    }
    printf("%.2f\n",l);
    return 0;
}