Code 1035 火车停留【最大费用最大流】

亦凉 2022-08-13 06:00 100阅读 0赞

题目：[Code 1035 火车停留][Code 1035]

题目：中文题目，直接读吧

分析：读题之后发现是让费用最大，不容易考虑到费用流，其实费用最大和最小是一样的，费用最大的话可以把费用变为负值求最小的。

建图方法：

超级源点 ss 连接 s ，容量为 n ，费用为0

把每个列车拆成两个点 i 和 ii ，之间建边容量为1 ，费用为给车站交的钱的相反数

s 连接 i ，容量inf ，费用0

ii 连接 t ，容量inf ，费用0

所有时刻末点在初点前面的，枚举建边，容量为1，费用0

然后求一次费用流，其相反数就是ans

AC代码：

#include <cstdio>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <cstring>
    #include <queue>
    #include <string>
    #include <map>
    using namespace std;
    #define Del(a,b) memset(a,b,sizeof(a))
    const int inf = 0x3f3f3f3f;
    const int N = 220;
    struct Node
    {
        int from,to,cap,flow;
        double cost;
    };
    vector<Node> e;
    vector<int> v[N];
    int vis[N];
    double dis[N];
    int p[N],a[N];  //p保存father，a保存cap
    void Clear(int x)
    {
        for(int i=0;i<=x;i++)
            v[i].clear();
        e.clear();
    }
    void add_Node(int from,int to,int cap,double cost)  //shaB
    {
        e.push_back((Node){from,to,cap,0,cost});
        e.push_back((Node){to,from,0,0,-cost});
        int len = e.size()-1;
        v[to].push_back(len);
        v[from].push_back(len-1);
    }
    bool BellmanFord(int s,int t,int& flow,double& cost)
    {
        for(int i=0;i<=N;i++)
            dis[i] = 1000000000;
        Del(vis,0);
        dis[s] = 0;
        vis[s] = 1;
        p[s] = 0;
        a[s] = inf;
        queue<int> q;
        q.push(s);
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            vis[u] = 0;
            for(int i=0; i<v[u].size(); i++)
            {
                Node& g = e[v[u][i]];
                if(g.cap>g.flow && dis[g.to] > dis[u]+g.cost)
                {
                    dis[g.to] = dis[u] + g.cost;
                    //printf("%.5lf\n",g.cost);
                    p[g.to] = v[u][i];  //保存前驱
                    a[g.to] = min(a[u],g.cap-g.flow);
                    if(!vis[g.to])
                    {
                        q.push(g.to);
                        vis[g.to]=1;
                    }
    
                }
            }
        }
        if(dis[t] == 1000000000)
            return false;
        flow += a[t];
        cost += dis[t]*a[t];
        int u = t;
        while(u!=s)
        {
            e[p[u]].flow += a[t];
            e[p[u]^1].flow -= a[t];
            u = e[p[u]].from;
        }
        return true;
    }
    double Min_Cost(int s,int t)
    {
        int flow=0;
        double cost = 0;
        while(BellmanFord(s,t,flow,cost));
        return cost;
    }
    struct Tree{
        int fir,sec;
        double val;
    };
    Tree kf[200];
    int main()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            int ss = 0 , s = 1;
            int t = 2*m + 3 ,tt = t+1;
            for(int i=1;i<=m;i++)
            {
                scanf("%d%lf%d",&kf[i].fir,&kf[i].val,&kf[i].sec);
                kf[i].sec+=kf[i].fir;
                add_Node(s,2*i,inf,0);
                double cs = kf[i].val * 0.01;
                //printf("%.5lf \n",cs);
                add_Node(2*i,2*i+1,1,-cs);
                add_Node(2*i+1,t,inf,0);
            }
            for(int i=1;i<=m;i++)
            {
                for(int j=1;j<=m;j++)  //注意这里
                {
                    if(i==j)
                        continue;
                    if(kf[j].fir>kf[i].sec)
                        add_Node(i*2+1,j*2,1,0);
                }
            }
            add_Node(ss,s,n,0.0);
            double ans = Min_Cost(ss,t);
            printf("%.2lf\n",-ans);
            Clear(tt);
        }
        return 0;
    }

[Code 1035]: http://codevs.cn/problem/1035/