nowcoder 206A - Birthday - [最小费用最大流]

题目链接：https://www.nowcoder.com/acm/contest/206/A

题目描述
恬恬的生日临近了。宇扬给她准备了一个蛋糕。
正如往常一样，宇扬在蛋糕上插了n支蜡烛，并把蛋糕分为m个区域。因为某种原因，他必须把第i根蜡烛插在第ai个区域或第bi个区域。区域之间是不相交的。宇扬在一个区域内同时摆放x支蜡烛就要花费x2的时间。宇扬布置蛋糕所用的总时间是他在每个区域花的时间的和。
宇扬想快些见到恬恬，你能告诉他布置蛋糕最少需要多少时间吗？
输入描述:
第一行包含两个整数n，m（1 ≤ n ≤ 50， 2≤ m≤ 50）。
接下来n行，每行两个整数ai,bi（1 ≤ ai, bi ≤ m）。
输出描述:
一个整数表示答案。
示例1
输入
3 3
1 2
1 2
1 2
输出
5
示例2
输入
3 3
1 2
2 3
1 3
输出
3

题解：

一开始有考虑从源点 $s$ 出发，连 $n$ 条流量上限为 $1$ 的边到左侧 $n$ 个节点（$n$ 根蜡烛），右侧 $m$ 个区域作为 $m$ 个节点，并向汇点 $t$ 连 $m$ 条边，

而从左侧到右侧的连边则根据题目所给的 $a[i],b[i]$ 进行，最后跑最小费用最大流，但是没能想到如何处理费用放弃了。

看了题解之后，感觉建图还是比较巧妙的，

考虑上面的思路，对于原本是右侧 $m$ 个区域作为节点，现在将这 $m$ 个节点中任意第 $j$ 个节点，都拆分成 $n$ 个节点，将其看成一组，称作第 $j$ 组，

对于原本的第 $i$ 根蜡烛，原来是有两条流量上限为 $1$ 的出弧，分别连向右侧的第 $a[i]$ 和第 $b[i]$ 个节点的，

现在拆点后，就变成了 $2 \times n$ 条出弧了，其中 $n$ 条出弧连向第 $a[i]$ 组，$n$ 条出弧连向第 $b[i]$ 组，流量上限不变，

同时，对于右侧每一组的 $n$ 个节点，第 $1$ 个节点的所有入弧费用都设为 $1^2 - 0^2 = 1$，第 $2$ 个节点的所有入弧费用都设为 $2^2 - 1^2 = 3$，依次类推；

这样一来，就像蛋糕上每个区域，我都分出了 $n$ 个空位，由于最小费用的限制，所以插蜡烛只会往费用最小的空位插，就可以保证答案的正确性。

AC代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

const int INF=0x3f3f3f3f;

struct Edge{

    int u,v,cap,flow,cost;

};

struct MCMF

{

    int s,t; //源点汇点

    vector<Edge> E;

    vector<int> G[maxn];

    void init(int l,int r)

    {

        E.clear();

        for(int i=l;i<=r;i++) G[i].clear();

    }

    void addedge(int from,int to,int cap,int cost)

    {

        E.push_back((Edge){from,to,cap,,cost});

        E.push_back((Edge){to,from,,,-cost});

        G[from].push_back(E.size()-);

        G[to].push_back(E.size()-);

    }

    int d[maxn],vis[maxn];

    int aug[maxn],pre[maxn];

    bool spfa(int s,int t,int &flow,int &cost)

    {

        memset(d,INF,sizeof(d));

        memset(vis,,sizeof(vis));

        queue<int> q;

        q.push(s);

        d[s]=, vis[s]=, pre[s]=, aug[s]=INF;

        while(!q.empty())

        {

            int now=q.front(); q.pop();

            vis[now]=;

            for(int i=;i<G[now].size();i++)

            {

                Edge& e=E[G[now][i]]; int nxt=e.v;

                if(e.cap>e.flow && d[nxt]>d[now]+e.cost)

                {

                    d[nxt]=d[now]+e.cost;

                    pre[nxt]=G[now][i];

                    aug[nxt]=min(aug[now],e.cap-e.flow);

                    if(!vis[nxt])

                    {

                        q.push(nxt);

                        vis[nxt]=;

                    }

                }

            }

        }

        if(d[t]==INF) return ;

        flow+=aug[t];

        cost+=d[t]*aug[t];

        for(int i=t;i!=s;i=E[pre[i]].u)

        {

            E[pre[i]].flow+=aug[t];

            E[pre[i]^].flow-=aug[t];

        }

        return ;

    }

    int mc,mf;

    void solve()

    {

        int flow=,cost=;

        while(spfa(s,t,flow,cost));

        mc=cost;

        mf=flow;

    }

}mcmf;

int n,m;

int a[],b[];

int main()

{

    cin>>n>>m;

    for(int i=;i<=n;i++) cin>>a[i]>>b[i];

    mcmf.init(,n+n*m+);

    mcmf.s=;

    mcmf.t=n+n*m+;

    for(int i=;i<=n;i++)

    {

        mcmf.addedge(mcmf.s,i,,);

        for(int j=,u,v;j<=n;j++)

        {

            u=i,v=n+(a[i]-)*n+j;

            mcmf.addedge(u,v,,*j-);

            u=i,v=n+(b[i]-)*n+j;

            mcmf.addedge(u,v,,*j-);

        }

    }

    for(int i=;i<=m;i++)

        for(int j=;j<=n;j++)

            mcmf.addedge(n+(i-)*n+j,mcmf.t,,);

    mcmf.solve();

    printf("%d\n",mcmf.mc);

}

巴特西

nowcoder 206A - Birthday - [最小费用最大流]

最新文章

热门文章