[最小费用流][平方费用][拆点/边建图] 2018camp Birthday

题目链接：http://newoj.acmclub.cn/problems/2053

只要能想到用最小费用最大流去做，建图还是相对好想的：左边n个点表示n根蜡烛，右边n*m个点（或者m个点但是每个点有n条边连汇点，二者是等价的），然后源点连左边n个点之间cost为0容量为1，表示每个蜡烛最多被用一次，然后从左边到右边i到ai所有的n个分点连容量为1  cost为2*k-1的边，最后右边每个点跟汇点连容量为1  cost为0的边，最后跑最小费用最大流即可。

平方费用处理的话也不难毕竟看过lrj书上的处理平方费用的方法。。。这种平方费用的话可以拆点也可以拆边，但是思路都是新弄出来的边cost都是当流量从i到i+1的时候的增量，也就是i^2-(i-1)^2，因为这个差值是随着i增大而增大的，所以最大流增加的时候一定是从小到大选择这些边的，而这些边的cost从小到大依次选择就可以累加出来x^2，也就是与原来的要求等效了。

 

#include

using namespace std;

typedef long long LL;
const int maxn=2e5+100;
const int mod=1e9+7;

const int MAXN = 2600+5;
const int MAXM = 127550+5;
const int INF = 0x3f3f3f3f;
struct Edge
{
    int to,next,cap,flow,cost;
    Edge(int _to = 0,int _next = 0,int _cap = 0,int _flow = 0,int _cost = 0):
        to(_to),next(_next),cap(_cap),flow(_flow),cost(_cost) {}
} edge[MAXM];
struct ZKW_MinCostMaxFlow
{
    int head[MAXN],tot;
    int cur[MAXN];
    int dis[MAXN];
    bool vis[MAXN];
    int ss,tt,N;//源点、汇点和点的总个数（编号是0∼N-1）, 不需要额外赋值，
//调用会直接赋值
    int min_cost, max_flow;
    void init()
    {
        tot = 0;
        memset(head,-1,sizeof(head));
    }
    void addedge(int u,int v,int cap,int cost)
    {
        edge[tot] = Edge(v,head[u],cap,0,cost);
        head[u] = tot++;
        edge[tot] = Edge(u,head[v],0,0,-cost);
        head[v] = tot++;
    }
    int aug(int u,int flow)
    {
        if(u == tt)
            return flow;
        vis[u] = true;
        for(int i = cur[u]; i != -1; i = edge[i].next)
        {
            int v = edge[i].to;
            if(edge[i].cap > edge[i].flow && !vis[v] && dis[u] ==dis[v] + edge[i].cost)
            {
                int tmp = aug(v,min(flow,edge[i].cap-edge[i].flow));
                edge[i].flow += tmp;
                edge[i^1].flow -= tmp;
                cur[u] = i;
                if(tmp)
                    return tmp;
            }
        }
        return 0;
    }
    bool modify_label()
    {
        int d = INF;
        for(int u = 0; u < N; u++)
            if(vis[u])
                for(int i = head[u]; i != -1; i = edge[i].next)
                {
                    int v = edge[i].to;
                    if(edge[i].cap>edge[i].flow && !vis[v])
                        d = min(d,dis[v]+edge[i].cost-dis[u]);
                }
        if(d == INF)
            return false;
        for(int i = 0; i < N; i++)
            if(vis[i])
            {
                vis[i] = false;
                dis[i] += d;

            }
        return true;
    }
    /*
    * 直接调用获取最小费用和最大流
    * 输入: start-源点，end-汇点，n-点的总个数（编号从0 开始）
    * 返回值: pair 第一个是最小费用，第二个是最大流
    */
    pair mincostmaxflow(int start,int end,int n)
    {
        ss = start, tt = end, N = n;
        min_cost = max_flow = 0;
        for(int i = 0; i < n; i++)
            dis[i] = 0;
        while(1)
        {
            for(int i = 0; i < n; i++)
                cur[i] = head[i];
            while(1)
            {
                for(int i = 0; i < n; i++)
                    vis[i] = false;
                int tmp = aug(ss,INF);
                if(tmp == 0)
                    break;
                max_flow += tmp;
                min_cost += tmp*dis[ss];
            }
            if(!modify_label())
                break;
        }
        return make_pair(min_cost,max_flow);
    }
} solve;

int main()
{
    int n,m,a,b,t;
    cin>>n>>m;
    t=n+n*m+1;
    solve.init();//important
    for (int i=1;i<=n;i++)
    {
        cin>>a>>b;
        solve.addedge(0,i,1,0);
        for (int k=1;k<=m;k++)
            solve.addedge(n+(i-1)*m+k,t,1,0);//error1
        for (int k=1;k<=n;k++)
        {
            solve.addedge(i,n+(a-1)*n+k,1,2*k-1);
            solve.addedge(i,n+(b-1)*n+k,1,2*k-1);
        }
    }

    pair ans=solve.mincostmaxflow(0,t,t+1);
    cout<