昆明猫咪科技网站建设,零基础学wordpress pdf下载,网上找客户有哪些网站,用电脑做网站ACM模板 目录概念做法例题概念
选择一个子图G′(V′,E′)G(V,E)G′(V′,E′)#xff0c;其中对于任意一条边的两个端点必须在所选的点集中#xff0c;最大化∣E′∣∣V′∣\frac{|E|}{|V|}∣V′∣∣E′∣
做法
利用01分数规划二分即最大化 ∣E′∣−g∣V′∣|E|-g|V|∣E…ACM模板 目录概念做法例题概念
选择一个子图G′(V′,E′)G(V,E)G′(V′,E′)其中对于任意一条边的两个端点必须在所选的点集中最大化∣E′∣∣V′∣\frac{|E|}{|V|}∣V′∣∣E′∣
做法
利用01分数规划二分即最大化 ∣E′∣−g∣V′∣|E|-g|V|∣E′∣−g∣V′∣ 也就是最小化g∣V′∣−∣E′∣∑v∈V′g−∑v∈V′1∑v∈V′g−12(∑v∈V′dv−c[V′,V′ˉ])12(∑v∈V′(2g−dv)c[V′,V′ˉ])g|V|-|E|\sum_{v\in V}g-\sum_{v\in V}1\sum_{v\in V}g-\frac{1}{2}(\sum_{v\in V}d_v-c[V,\bar{V}])\frac 1 2(\sum_{v\in V}(2g-d_v)c[V,\bar{V}])g∣V′∣−∣E′∣v∈V′∑g−v∈V′∑1v∈V′∑g−21(v∈V′∑dv−c[V′,V′ˉ])21(v∈V′∑(2g−dv)c[V′,V′ˉ]) 我们发现除了割边还有一个东西即∑v∈V′(2g−dv)\sum_{v\in V}(2g-d_v)∑v∈V′(2g−dv)只需要将每个点连向汇点一条容量是2g−dv2g-d_v2g−dv的边即可让构建的割的容量是上述式子。因为对于V′VV′中的点要求与源点SSS放在一起那么只要它与汇点存在边就会对割的容量由贡献。
建图原图中的点与边的容量都是1再加上所有点向汇点连边容量是2g−dv2g-d_v2g−dv。 那么构建出的网络流的割的容量c[S,T]2(g∣V′∣−∣E′∣)c[S,T]2(g|V|-|E|)c[S,T]2(g∣V′∣−∣E′∣) 于是g∣V′∣−∣E′∣12c[S,T]g|V|-|E|\frac{1}{2}c[S,T]g∣V′∣−∣E′∣21c[S,T] 即求最小割。
为了防止连向汇点的边权2g−dv2g-d_v2g−dv是负值需要增添一个偏移量UUU 重新建图即①源点向每个点连边容量是UUU②原图中的边容量是1③每个点向汇点连边容量是2g−dvU2g-d_vU2g−dvU 可证g∣V′∣−∣E′∣12(c[S,T]−nU)g|V|-|E|\frac{1}{2}(c[S,T]-nU)g∣V′∣−∣E′∣21(c[S,T]−nU)
最初需要最大化的值即∣E′∣−g∣V′∣nU−c[S,T]2|E|-g|V|\frac{nU-c[S,T]}{2}∣E′∣−g∣V′∣2nU−c[S,T]
不难看出如果我们这里把边看成点选边必须选择两个端点的限制可以加到边上即边向两个端点连单向边即可以转化为最大权闭合图问题
类型建图点数建图边数最大密度子图|V|2|V||E|最大权闭合图|V||E||V|3|E|
如果存在边权密度∑e∈EWe∣V∣\frac{\sum_{e\in E} W_e}{|V|}∣V∣∑e∈EWe dvd_vdv记为该点出边权值和而不是出度即可
若存在点权和边权密度∑v∈Vpv∑e∈EWe∣V∣\frac{\sum_{v\in V}p_v\sum_{e\in E} W_e}{|V|}∣V∣∑v∈Vpv∑e∈EWe ①dvd_vdv记为该点出边权值和 ②连向汇点和源点的边容量是2g−dv−2pvU2g-d_v-2p_vU2g−dv−2pvU
例题
#includeiostream
#includealgorithm
#includecstring
using namespace std;
const int N5010,M(500002*N)*210,INF0x3f3f3f3f;
int n,m;
int h[N],e[M],ne[M],f[M],idx;
int S,T,d[N],q[N],cur[N];
int deg[N],p[N];
void add(int a,int b,int c1,int c2)
{e[idx]b,ne[idx]h[a],f[idx]c1,h[a]idx;e[idx]a,ne[idx]h[b],f[idx]c2,h[b]idx;
}
bool bfs()
{memset(d,-1,sizeof d);int tt0,hh0;q[S]0,cur[S]h[S],d[S]0;while(hhtt){int tq[hh];for(int ih[t];i!-1;ine[i]){int je[i];if(d[j]-1f[i]){d[j]d[t]1;cur[j]h[j];if(jT) return 1;q[tt]j;}}}return 0;
}
int dfs(int uS,int flowINF)
{if(uT) return flow;int rmnflow;for(int icur[u];i!-1rmn;ine[i]){cur[u]i;int je[i];if(d[j]d[u]1f[i]){int tdfs(j,min(f[i],rmn));if(!t) d[j]-1;f[i]-t,f[i^1]t,rmn-t;}}return flow-rmn;
}
int dinic()
{int r0;while(bfs()) rdfs();return r;
}
int main()
{cinnm;memset(h,-1,sizeof h);S0,Tn1;for(int i1;in;i) cinp[i],p[i]*-1;while(m--){int a,b,c;cinabc;add(a,b,c,c);deg[a]c,deg[b]c;//记录出边权值和}int U0;for(int i1;in;i) Umax(U,2*p[i]deg[i]);for(int i1;in;i) add(S,i,U,0),add(i,T,U-2*p[i]-deg[i],0);cout(U*n-dinic())/2\n;return 0;
}
