1 条题解

  • 1
    @ 2020-08-12 21:17:00

    看腻了简单版的 \(A+B\),来个费用流。

    struct node
    {
    int to,dis;
    bool operator < (const node &rhs) const
    {
    return dis>rhs.dis;
    }
    };
    int d[10],preu[10],pree[10];
    bool inq[10];
    int e=1,w[10],r[10],first[10],next[10],cost=0,flow=0,tail[10],h[10];
    void link(int u,int v,int re,int weight)
    {
    next[++e]=first[u];
    first[u]=e;
    tail[e]=v;
    r[e]=re;
    w[e]=weight;
    next[++e]=first[v];
    first[v]=e;
    tail[e]=u;
    r[e]=0;
    w[e]=-weight;
    }
    int s=1,t=3;
    bool vis[100050];
    inline void dijkstra()
    {
    for (int i=1;i<=5;i++)
    {
    vis[i]=0;
    d[i]=1000000;
    }
    d[s]=0;
    priority_queue <pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
    q.empty();
    q.push(pair<int,int>(0,s));
    while (!q.empty())
    {
    pair <int,int> rhs=q.top();
    q.pop();
    int u=rhs.second;
    if (vis[u])
    continue;
    for (int i=first[u];i;i=next[i])
    {
    int v=tail[i];
    if (r[i]>0 && d[v]>d[u]+w[i]+h[u]-h[v])
    {
    d[v]=d[u]+w[i]+h[u]-h[v];
    preu[v]=u;
    pree[v]=i;
    q.push(pair<int,int>(d[v],v));
    }
    }
    }
    }
    inline void MinCostMaxFlow()
    {
    memset(h,0,sizeof(h));
    while (1)
    {
    dijkstra();
    if (d[t]==1000000)
    break;
    else
    {
    for (int u=1;u<=3;u++)
    h[u]+=d[u];
    int delta=1000000;
    for (int u=t;u!=s;u=preu[u])
    {
    int e=pree[u];
    delta=min(delta,r[e]);
    }
    flow+=delta;
    cost+=delta*h[t];
    for (int u=t;u!=s;u=preu[u])
    {
    int e=pree[u];
    r[e]-=delta;
    r[e^1]+=delta;
    }
    }
    }
    }
    inline void solve()
    {
    int a=read(),b=read();
    link(1,2,1,a);
    link(2,3,1,b);
    MinCostMaxFlow();
    cout << cost << endl;
    }

  • 1

信息

ID
1002
难度
1
分类
模拟 点击显示
标签
(无)
递交数
22
已通过
5
通过率
23%
被复制
1
上传者