上海专业的网页设计公司,百度推广优化怎么做的,商丘网站建设案例,怎样建设一个购物网站参考博客#xff1a;最小割浅谈
关于最小割 常用描述 表述一#xff1a;删去若干条边使得源点到汇点不连通#xff0c;求删边的权值和的最小可能值。 表述二#xff1a;将点集分为(S,T)(S,T)(S,T)#xff0c;记所有从SSS中出发到TTT中的边的权值和为c(S,T)c(S,T)c(S,T)最小割浅谈
关于最小割 常用描述 表述一删去若干条边使得源点到汇点不连通求删边的权值和的最小可能值。 表述二将点集分为(S,T)(S,T)(S,T)记所有从SSS中出发到TTT中的边的权值和为c(S,T)c(S,T)c(S,T)求c(S,T)c(S,T)c(S,T)的最小值。 求最小割 a. 以权值为容量该网络最大流的值即为最小割的值 b. 在残量网络中从源点出发进行一次增广BFS即得到一个分割。该分割是一个最小割。
题型1对求最小割原理的理解
[AHOI2009]最小割 摘自此Blog
[SDOI2014]LIS 摘自此Blog
#includealgorithm
#includeiostream
#includecstring
#includecstdio
#includequeue
#define re register
#define maxn 1505
#define LL long long
#define inf 999999999
inline int max(int a,int b){return ab?a:b;}
inline int min(int a,int b){return ab?a:b;}
inline int read()
{char cgetchar();int x0;while(c0||c9) cgetchar();while(c0c9) x(x3)(x1)c-48,cgetchar();return x;
}
struct node{int a,b,c,rk;}g[maxn];
inline int cmp(node A,node B) {return A.cB.c;}
struct E{int v,nxt,w,f;}e[maxn*maxn];
int n,num1,S,T,Test;
int ans[maxn],cnt,id[maxn],vis[maxn];
int d[maxn],dp[maxn],head[maxn],cur[maxn],in[maxn],out[maxn];
inline void add(int x,int y,int z) {e[num].vy;e[num].nxthead[x];head[x]num;e[num].wz;}
inline void C(int x,int y,int z) {add(x,y,z),add(y,x,0);}
inline int check(int s,int t)
{std::queueint q;memset(vis,0,sizeof(vis));q.push(s);vis[s]1;while(!q.empty()){int kq.front();q.pop();if(kt) return 1;for(re int ihead[k];i;ie[i].nxt)if(!vis[e[i].v]e[i].we[i].f) q.push(e[i].v),vis[e[i].v]1;}return 0;
}
inline int BFS(int s,int t)
{std::queueint q;memcpy(cur,head,sizeof(head));memset(d,0,sizeof(d));d[s]1,q.push(s);while(!q.empty()){int kq.front();q.pop();for(re int ihead[k];i;ie[i].nxt)if(!d[e[i].v]e[i].we[i].f) {d[e[i].v]d[k]1;if(e[i].vt) return 1;q.push(e[i].v);}}return d[t];
}
int dfs(int x,int now,int t)
{if(xt||!now) return now;int flow0,ff;for(re int icur[x];i;ie[i].nxt)if(d[e[i].v]d[x]1){ffdfs(e[i].v,min(now,e[i].w-e[i].f),t);if(ff0) continue;now-ff,flowff;e[i].fff,e[i^1].f-ff;if(!now) break;}return flow;
}
int main()
{Testread();while(Test--){nread();cnt0;num1;memset(head,0,sizeof(head));for(re int i1;in;i) g[i].aread(),dp[i]1;for(re int i1;in;i) g[i].bread(),g[i].rki;for(re int i1;in;i)for(re int j1;ji;j) if(g[j].ag[i].a) dp[i]max(dp[j]1,dp[i]);int tot0;for(re int i1;in;i) totmax(tot,dp[i]);//dp求LIS T0;for(re int i1;in;i) in[i]T;for(re int i1;in;i) out[i]T;T;for(re int i1;in;i) C(in[i],out[i],g[i].b),id[i]num;for(re int i1;in;i) if(dp[i]1) C(S,in[i],inf);for(re int i1;in;i) if(dp[i]tot) C(out[i],T,inf);for(re int i1;in;i)for(re int j1;ji;j) if(g[j].ag[i].adp[j]1dp[i]) C(out[j],in[i],inf);tot0;while(BFS(S,T)) totdfs(S,inf,T);//建图跑最小割 for(re int i1;in;i) g[i].cread();printf(%d ,tot);std::sort(g1,gn1,cmp);for(re int i1;in;i){int kg[i].rk;if(check(in[k],out[k])) continue;ans[cnt]k;while(BFS(T,out[k])) dfs(T,inf,out[k]);while(BFS(in[k],S)) dfs(in[k],inf,S);e[id[k]].we[id[k]^1].w0;e[id[k]].fe[id[k]^1].f0;//退流排除和当前所选边等价的边的影响 }printf(%d\n,cnt);std::sort(ans1,anscnt1);for(re int i1;icnt;i) printf(%d ,ans[i]);putchar(10);}return 0;
}题型2最下生成树相关
例题这里有
题型3对点的分割 转 对边的分割
[HNOI2013] 切糕
题型4最小点割集
最小点割集是指 给出一张有向图无向图和两个点S、T每个点都有一个正数点权求一个不包含点S、T的权值和最小的点集使得删掉点集中的所有点后S无法到达T。
求法 对于这个问题我们将每一个点拆成两个点一个为入点一个为出点这两个点之间有一条边权为原图中点权的有向边从入点指向出点。对于原图中的边x→yx\to yx→y我们将其更改为x的出点→y\to y→y的入点。在转化完的图上跑最小割就是原图的最小点割集。
题型5最小割树——求任意两点的最小割
最小割树
#includebits/stdc.h
using namespace std;
int n,m,node[505],dep[505],fa[505][10],mn[505][10];
int cnt,top[505],to[1005],len[1005],nex[1005];
int read()
{int re0;char chgetchar();while(!isdigit(ch)) chgetchar();while(isdigit(ch)) re(re3)(re1)ch-0,chgetchar();return re;
}
void add_edge(int x,int y,int z)
{to[cnt]y,len[cnt]z,nex[cnt]top[x],top[x]cnt;to[cnt]x,len[cnt]z,nex[cnt]top[y],top[y]cnt;
}
namespace GHT
{int s,t;int tot,cur[505],dep[505],col[505],col_bucket[505];int cnt1,top[505],to[3005],cap[3005],flow[3005],nex[3005];void add_edge(int x,int y,int z){to[cnt]y,cap[cnt]z,flow[cnt]0,nex[cnt]top[x],top[x]cnt;to[cnt]x,cap[cnt]z,flow[cnt]0,nex[cnt]top[y],top[y]cnt;//注意这里 }bool BFS(){memset(cur,0,sizeof cur);memset(dep,0,sizeof dep);dep[s]1,cur[s]top[s];queueintQ;Q.push(s);while(!Q.empty()){int nowQ.front();Q.pop();for(int itop[now];i;inex[i])if(!dep[to[i]]cap[i]flow[i]){dep[to[i]]dep[now]1;cur[to[i]]top[to[i]];Q.push(to[i]);}}return dep[t]!0;}int DFS(int now,int rest){if(nowt) return rest;int re0;for(int icur[now];i;inex[i])if(dep[to[i]]dep[now]1cap[i]flow[i]){int lzqDFS(to[i],min(rest,cap[i]-flow[i]));if(lzq){rest-lzq,relzq;flow[i]lzq,flow[i^1]-lzq;//注意这里 if(!rest) break;}}return re;}int Dinic(int x,int y){int re0;sx,ty;for(int i1;icnt;i) flow[i]0;while(BFS()) reDFS(s,0x3f3f3f3f);return re;}void get_color(int now,int color){col[now]color;for(int itop[now];i;inex[i])if(cap[i]flow[i]col[to[i]]!color)//注意这里 get_color(to[i],color);}void build(int l,int r){if(lr) return ;int xnode[l],ynode[l1];int cutDinic(x,y);get_color(x,tot);int Ll,Rr;for(int il;ir;i)if(col[node[i]]tot) col_bucket[L]node[i];else col_bucket[R--]node[i];for(int il;ir;i) node[i]col_bucket[i];::add_edge(x,y,cut);build(l,L-1);build(R1,r);}
}
void dfs(int now)
{for(int i1;i9;i){fa[now][i]fa[fa[now][i-1]][i-1];mn[now][i]min(mn[now][i-1],mn[fa[now][i-1]][i-1]);}for(int itop[now];i;inex[i]){if(to[i]fa[now][0]) continue;dep[to[i]]dep[now]1,fa[to[i]][0]now,mn[to[i]][0]len[i];dfs(to[i]);}
}
int getcut(int x,int y)
{int reINT_MAX;if(dep[x]dep[y]) swap(x,y);for(int i9;i0;i--) if(dep[fa[x][i]]dep[y]) remin(re,mn[x][i]),xfa[x][i];if(xy) return re;for(int i9;i0;i--) if(fa[x][i]!fa[y][i]) remin(re,min(mn[x][i],mn[y][i])),xfa[x][i],yfa[y][i];return min(re,min(mn[x][0],mn[y][0]));
}
int main()
{nread(),mread();while(m--){int xread(),yread(),zread();GHT::add_edge(x,y,z);}for(int i1;in;i) node[i]i;GHT::build(1,n);dep[1]1;dfs(1);mread();while(m--){int xread(),yread();printf(%d\n,getcut(x,y));}return 0;
}题型6最大权闭合子图
闭合子图指的是对于有向图我们选择一些点在这个点集之中没有一个点的出边指向非此点集中的点但是可以有其他点的出边指向这个点集之中。所说的最大权闭合子图就是在这个图的所有闭合子图中点权和最大的。
求法 建立源点向每一个点权为正的点连边边权为该点的权值。建立汇点向每一个点权为负连边边权为该点的权值的绝对值。原图中的边进行保留边权为infinfinf。最大权闭合子图就是所有的点权为正的点权和减去最小割。 题型7划分点集
记(u→v,w)(u\to v,w)(u→v,w)为一条从uuu到vvv权值为www的边。
基础模型
把nnn个点划分到两个集合A,BA,BA,B。给出若干形如 “若…则有…的代价/贡献” 的条件。问最大贡献/最小代价是多少。
如果题目问的是最小代价直接按下面方法连边求最小割。 如果题目问的是最大贡献答案为∑所有可能贡献−最小代价(最小割)\sum 所有可能贡献-最小代价(最小割)∑所有可能贡献−最小代价(最小割)。
定义和SSS相连的点划到AAA集合和TTT相连的点划到BBB集合那么我们可以按下面的方法处理题目给出的条件
条件-表述1若把iii划到AAA则要付出bib_ibi的代价若把iii划到BBB则要付出aia_iai的代价 条件-表述2若把iii划到BBB则有bib_ibi的贡献若把iii划到AAA,则有aia_iai的贡献 方案(i→T,bi)(i\to T,b_i)(i→T,bi),(S→i,ai)(S\to i,a_i)(S→i,ai)条件-表述1若点集XXX中有元素划到BBB则要付出ccc的代价 条件-表述2若点集XXX中元素全部划到AAA则有ccc的贡献 方案(S→new,c),∀i∈X(new→i,inf)(S\to new,c),\forall i\in X(new\to i,inf)(S→new,c),∀i∈X(new→i,inf)条件-表述1若点集XXX中有元素划到AAA则要付出ddd的代价 条件-表述2若点集XXX中元素全部划到BBB则有ddd的贡献 方案∀i∈X(i→new,inf),(new→T,d)\forall i\in X(i\to new,inf),(new\to T,d)∀i∈X(i→new,inf),(new→T,d)条件若点集XXX中有元素划到BBB点集YYY中有元素划到AAA则要付出eee的代价 常见形式若点iii划到BBB点jjj划到AAA则要付出eee的代价 方案∀i∈X(new1→i,inf)\forall i\in X(new1\to i,inf)∀i∈X(new1→i,inf),∀j∈Y(j→new2,inf)\forall j\in Y(j\to new2,inf)∀j∈Y(j→new2,inf),(new2→new1,e)(new2\to new1,e)(new2→new1,e)条件若点集XXX中有元素划到AAA点集YYY中有元素划到BBB则要付出fff的代价 常见形式若点iii划到AAA点jjj划到BBB则要付出fff的代价 方案∀i∈X(i→new1,inf)\forall i\in X(i\to new1,inf)∀i∈X(i→new1,inf),∀j∈Y(new2→j,inf)\forall j\in Y(new2\to j,inf)∀j∈Y(new2→j,inf),(new1→new2,f)(new1\to new2,f)(new1→new2,f)
[Shoi2007]Vote 善意的投票
BZOJ3438: 小M的作物
[BZOJ3218]a b Problem
处理变形问题的trick黑白染色翻转源汇
对于“x,yx,yx,y必须划到不同集合” “x,yx,yx,y划到不同集合有ccc的贡献” “x,yx,yx,y划到相同集合有ddd的代价”这样的条件我们可以连边(x,y)(x,y)(x,y)黑白染色后x,yx,yx,y一定一个是黑点一个是白点。
如果将其中一种颜色的点进行翻转源汇即原本应该连向SSS的边连向TTT原本应该连向TTT的边连向SSS那么“x,yx,yx,y在不同集合”就变成了“x,yx,yx,y在相同集合”“x,yx,yx,y在相同集合”就变成了“x,yx,yx,y在不同集合”
BZOJ1324Exca王者之剑BZOJ1475方格取数——二分图最大独立集
[BZOJ2132]圈地计划——翻转源汇
