傻瓜做网站软件/搜索引擎营销ppt

题目描述
恬恬的生日临近了。宇扬给她准备了一个蛋糕。
正如往常一样，宇扬在蛋糕上插了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

比较经典的费用流问题。

由于我们花费与流量之间的关系并不是线性的，所以我们不能直接算，我们要把边拆成流量为1的很多条，费用推一下即可。

然后最小费用最大流。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int inf=0x3f3f3f3f;
const int N=210,M=1e4+10;
int n,m,s,t,d[N],v[N],e[N];
int head[N],nex[M],to[M],w[M],flow[M],tot=1;
inline void ade(int a,int b,int c,int d){to[++tot]=b; flow[tot]=c; w[tot]=d; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c,int d){ade(a,b,c,d); ade(b,a,0,-d);
}
inline int spfa(){memset(d,inf,sizeof d); queue<int> q;	q.push(s); d[s]=0;int vis[N]={0};	vis[s]=1;while(q.size()){int u=q.front();	q.pop();	vis[u]=0;for(int i=head[u];i;i=nex[i]){if(flow[i]&&d[to[i]]>d[u]+w[i]){d[to[i]]=d[u]+w[i];v[to[i]]=u; e[to[i]]=i;if(!vis[to[i]])	q.push(to[i]),vis[to[i]]=1;}}}return d[t]!=inf;
}
int EK(){int res=0;while(spfa()){int mi=inf;for(int i=t;i!=s;i=v[i])	mi=min(mi,flow[e[i]]);for(int i=t;i!=s;i=v[i])	flow[e[i]]-=mi,flow[e[i]^1]+=mi;res+=mi*d[t];}return res;
}
signed main(){cin>>m>>n;	t=n+m+1;for(int i=1;i<=m;i++){int a,b;	cin>>a>>b;	add(s,i,1,0);	add(i,m+a,1,0); add(i,m+b,1,0);}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)	add(i+m,t,1,2*j-1);}cout<<EK()<<endl;return 0;
}