题目链接：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 imes 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=3000; 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,0,cost}); E.push_back((Edge){to,from,0,0,-cost}); G[from].push_back(E.size()-2); G[to].push_back(E.size()-1); } 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,0,sizeof(vis)); queue<int> q; q.push(s); d[s]=0, vis[s]=1, pre[s]=0, aug[s]=INF; while(!q.empty()) { int now=q.front(); q.pop(); vis[now]=0; for(int i=0;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]=1; } } } } if(d[t]==INF) return 0; 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]^1].flow-=aug[t]; } return 1; } int mc,mf; void solve() { int flow=0,cost=0; while(spfa(s,t,flow,cost)); mc=cost; mf=flow; } }mcmf; int n,m; int a[55],b[55]; int main() { cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]>>b[i]; mcmf.init(0,n+n*m+1); mcmf.s=0; mcmf.t=n+n*m+1; for(int i=1;i<=n;i++) { mcmf.addedge(mcmf.s,i,1,0); for(int j=1,u,v;j<=n;j++) { u=i,v=n+(a[i]-1)*n+j; mcmf.addedge(u,v,1,2*j-1); u=i,v=n+(b[i]-1)*n+j; mcmf.addedge(u,v,1,2*j-1); } } for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) mcmf.addedge(n+(i-1)*n+j,mcmf.t,1,0); mcmf.solve(); printf("%d ",mcmf.mc); }