2018CCPC秦皇岛站-A.Build(费用限制的最小割)

题目链接:2018CCPC秦皇岛站-A.Build

题意:

给一张图,然后对于每条边,最开始等级为0,然后最多可以升级至MAX[i]级,然后每升级一次的花费为C[i],相应的,破坏一条边的花费等于这条边的等级。然后给定预算F,问怎样升级,才能使1到n不连通的花费最大,求最大花费。

题解:

去年赛场上看了半天,没有任何思路,完全没想到是费用流,真的是铁憨憨。

实际上就是一个求一个有费用限制的图的最小割,我们直接建边,边的容量为MAX[i],花费为C[i],然后费用限制为F,我们每次spfa求出单位流量的最小花费之后,然后再取经过的路径的流量时,初值应该保证:minflow*dis[ed]<=F,然后再进行更新最小的流量,当最小流量为0时,退出即可。

参考代码:

#include <bits/stdc++.h>
// #define int long long
using namespace std;
typedef long long ll;
const int MAXN = 1e3 + 10;
const int MAXM = 1e4 + 10;
const int inf = 0x3f3f3f3f;
int n, m;
ll F;
struct EDGE
{
    int v, nxt, w;
    ll c;
} edge[MAXM << 3];
int fir[MAXN], ecnt;
void addedge(int u, int v, int w, ll c)
{
    edge[ecnt].v = v;
    edge[ecnt].w = w;
    edge[ecnt].c = c;
    edge[ecnt].nxt = fir[u];
    fir[u] = ecnt++;
    swap(u, v);
    edge[ecnt].v = v;
    edge[ecnt].w = 0;
    edge[ecnt].c = -c;
    edge[ecnt].nxt = fir[u];
    fir[u] = ecnt++;
}
struct node
{
    int id, v;
} pre[MAXN];
ll dis[MAXN];
bool used[MAXN];
bool SPFA(int st, int ed)
{
    queue<int> que;
    while (!que.empty())
        que.pop();
    memset(used, 0, sizeof(used));
    memset(dis, 0x3f, sizeof(dis));
    dis[st] = 0;
    used[st] = 1;
    que.push(st);
    while (!que.empty())
    {
        int u = que.front();
        que.pop();
        used[u] = 0;
        for (int i = fir[u]; i != -1; i = edge[i].nxt)
        {
            int v = edge[i].v;
            if (edge[i].w && dis[v] > dis[u] + edge[i].c)
            {
                dis[v] = dis[u] + edge[i].c;
                pre[v].v = u;
                pre[v].id = i;
                if (!used[v])
                {
                    que.push(v);
                    used[v] = 1;
                }
            }
        }
    }
    if (dis[ed] == 0x3f3f3f3f3f3f3f3f)
        return 0;
    return 1;
}
ll MCMF(int st, int ed)
{
    int flow = 0;
    ll mincost = 0;
    while (SPFA(st, ed))
    {
        int minflow = F / dis[ed];
        for (int i = ed; i != st; i = pre[i].v)
            minflow = min(minflow, edge[pre[i].id].w);
        F -= dis[ed] * minflow;
        flow += minflow;
        if (F < dis[ed])
            break;
        for (int i = ed; i != st; i = pre[i].v)
        {
            edge[pre[i].id].w -= minflow;
            edge[pre[i].id ^ 1].w += minflow;
        }
    }
    return flow;
}
int main()
{
    scanf("%d%d%lld", &n, &m, &F);
    memset(fir, -1, sizeof(fir));
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        ll c;
        scanf("%d%d%d%lld", &u, &v, &w, &c);
        addedge(u, v, w, c), addedge(v, u, w, c);
    }
    printf("%lld\n", MCMF(1, n));
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。