题目链接：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);
}
