信息网站制作,竞价推广代运营,建设工程施工合同在哪个网站,上海品牌营销策划公司排名ACM模板 目录概念建图证明模板题概念
闭合图中所有的点的出边必须指向内部的点
建图
原图的边在网络流中的边容量是INF#xff0c;如果点权是正#xff0c;那么源点向其连边#xff0c;容量是点权#xff1b;否则它向汇点连边#xff0c;容量是点权绝对值
证明
考虑最…ACM模板 目录概念建图证明模板题概念
闭合图中所有的点的出边必须指向内部的点
建图
原图的边在网络流中的边容量是INF如果点权是正那么源点向其连边容量是点权否则它向汇点连边容量是点权绝对值
证明
考虑最小割 [S,T][S,T][S,T]所求的满足条件的闭合子图为V1V_1V1
SV1∪{s}SV_1\cup \{ s \}SV1∪{s} TV2∪{t}TV_2\cup \{t \}TV2∪{t}其中V2V−V1V_2V-V_1V2V−V1 c[S,T]∑v∈V2wv∑v∈V1−(−wv)c[S,T]\sum_{v\in V_2^}w_v\sum_{v\in V_1^-}(-w_v)c[S,T]v∈V2∑wvv∈V1−∑(−wv)
而闭合子图的权值为 W(V1)∑v∈V1wv∑v∈V1−wv∑v∈V1wv−∑v∈V1−(−wv)W(V_1)\sum_{v\in V_1^}w_v\sum_{v\in V_1^-}w_v\sum_{v\in V_1^}w_v-\sum_{v\in V_1^-}(-w_v)W(V1)v∈V1∑wvv∈V1−∑wvv∈V1∑wv−v∈V1−∑(−wv)
于是有 c[S,T]W(V1)∑v∈V1wv∑v∈V2wv∑v∈Vwvc[S,T]W(V_1)\sum_{v\in V_1^}w_v\sum_{v\in V_2^}w_v\sum_{v\in V^}w_vc[S,T]W(V1)v∈V1∑wvv∈V2∑wvv∈V∑wv
即 W(V1)∑v∈Vwv−c[S,T]W(V_1)\sum_{v\in V^}w_v-c[S,T]W(V1)v∈V∑wv−c[S,T]
模板题
最大获利
#includeiostream
#includealgorithm
#includecstring
using namespace std;
const int N55010,M6*N,INF0x3f3f3f3f;
int n,m;
int h[N],e[M],ne[M],f[M],idx;
int S,T,d[N],q[N],cur[N];
void add(int a,int b,int c)
{e[idx]b,ne[idx]h[a],f[idx]c,h[a]idx;e[idx]a,ne[idx]h[b],f[idx]0,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,Tnm1;int s0;for(int i1;in;i){int p;cinp; add(i,T,p);}for(int i1;im;i){int a,b,c;cinabc;add(in,a,INF),add(in,b,INF);add(S,in,c);sc;}couts-dinic()\n;return 0;
}
