seo建站平台哪家好,广西省桂林市,宠物网站建站目标,网站建设费会计科目我的网络流7题 最大流2题#xff1a; 洛谷P2756 飞行员配对方案问题 分析 其实就是一个二分图匹配求最大匹配数的问题#xff0c;加一个源点和汇点#xff0c;再跑一遍网络流#xff0c;输出方案的时候检查一下有没有流经过即可#xff08;反向边是否非0#xff09;。 注… 我的网络流7题 最大流2题 洛谷P2756 飞行员配对方案问题 分析 其实就是一个二分图匹配求最大匹配数的问题加一个源点和汇点再跑一遍网络流输出方案的时候检查一下有没有流经过即可反向边是否非0。 注意每个点在向源点和汇点连边时要在输入完之后再连。否则会重复连。 #includebits/stdc.h
using namespace std;
#define N 205
#define M 30005
int to[M],head[N],nex[M],w[M],lev[N],tot1,cnt0,inf0x7f7f7f,s0,t101,n,cur[N];
struct node{ int u,v,bian; }e[M];
queueint q;
void add(int a,int b,int ww)
{tot; to[tot]b; w[tot]ww; nex[tot]head[a]; head[a]tot;if(ww0ba!t) e[cnt].biantot;
}
bool bfs()
{memset(lev,-1,sizeof(lev));lev[s]0; q.push(s);while(!q.empty()){int uq.front(); q.pop();for(int ihead[u];i!-1;inex[i]){int vto[i];if(w[i]0lev[v]-1)lev[v]lev[u]1,q.push(v);}}if(lev[t]!-1) return true;return false;
}
int dfs(int u,int flow)
{if(ut) return flow;int retflow;for(int icur[u];i!-1;inex[i]){cur[u]i;if(ret0) break;int vto[i];if(w[i]0lev[u]1lev[v]){int kdfs(v,min(w[i],ret));ret-k; w[i]-k; w[i^1]k; //异或运算2k^1(2k1) (2k1)^12k;}}return flow-ret;//最大限制 - 还剩的多少没流 流出去了多少
}
void dinic()
{int ans0;while(bfs()){for(int i0;i101;i) cur[i]head[i]; ansdfs(s,inf);}printf(%d\n,ans);
}
int main()
{int m,a,b;scanf(%d%d,m,n);memset(head,-1,sizeof(head));while(1){scanf(%d%d,a,b);if(a-1b-1) break;cnt;add(a,b,inf); add(b,a,0); e[cnt].ua; e[cnt].vb;}//一定要在后面建否则会重复建边 for(int i1;im;i) add(s,i,1),add(i,s,0);for(int im1;in;i) add(i,t,1),add(t,i,0);dinic();for(int i1;icnt;i)if(w[e[i].bian]!0) printf(%d %d\n,e[i].u,e[i].v);
}
/*
5 10
1 7
1 8
2 6
2 9
2 10
3 7
3 8
4 7
4 8
5 10
-1 -12 4
1 3
1 4
2 3
-1 -1
*/ View Code 洛谷P2765 魔术球问题 «问题描述 假设有n根柱子现要按下述规则在这n根柱子中依次放入编号为123...的球。 1每次只能在某根柱子的最上面放球。 2在同一根柱子中任何2个相邻球的编号之和为完全平方数。 试设计一个算法计算出在n根柱子上最多能放多少个球。例如在4 根柱子上最多可放11 个球。 n55 分析 首先这道题的主要限制在于球平方数考虑对球建边。将每个球拆成两部分第一部分对 s 连边第二部分对 t 连边 两部分间通过和为平方数的条件连边边权都为1。一个一个地加球加一次跑一次最大流如果在以前的基础上产生了新流说明加入的这个球能对已有的球产生平方和的联系即可以加在某一个球上面。加球一直到没有产生新流了说明需要加柱子了这时就将柱子一直到达到n个为止。 方案输出 每当新加一个柱子时记录最先放入柱子的球然后在找增广路的时候对每一个点记录下一个可行的点是谁类似于邻接表一样的链表式结构。然后输出的时候枚举柱子。 #includebits/stdc.h
using namespace std;
#define inf 2100000000
#define M 1000005
int to[M],nex[M],head[M],w[M],tot0,vis[M];
int nexxt[M],headd[M],lev[M],cur[M],sM-5,tM-4;
queueint q;
void add(int a,int b,int ww)
{to[tot]b; nex[tot]head[a]; head[a]tot; w[tot]ww;to[tot]a; nex[tot]head[b]; head[b]tot; w[tot]0;
}
bool bfs()
{memset(lev,-1,sizeof(lev));lev[s]0; q.push(s);while(!q.empty()){int uq.front(); q.pop();for(int ihead[u];i!-1;inex[i]){int vto[i];if(lev[v]-1 w[i]) lev[v]lev[u]1,q.push(v);}}return lev[t]!-1;
}
int dfs(int u,int flow)
{if(ut) return flow;int retflow;for(int ihead[u];i!-1;inex[i]){int vto[i];if(ret0) break;if(lev[v]lev[u]1w[i]0){int kdfs(v,min(ret,w[i]));nexxt[u1]v1;//记录一下这个球对应的下一个球是哪一个 因为存的时候*21了 所以要/2 不需要分奇偶讨论 ret-k; w[i]-k; w[i^1]k;}} return flow-ret;
}
int dinic()
{int ans0;while(bfs()){ansdfs(s,inf);} return ans;
}
int main()
{int n;scanf(%d,n);memset(head,-1,sizeof(head));int now0,zhu0;//headd[1]1;while(zhun){now;add(s,now1,1); add(now1|1,t,1);for(int isqrt(now)1;i*inow*2;i)add((i*i-now)1,now1|1,1);int tmpdinic();if(!tmp) headd[zhu]now;}printf(%d\n,now-1);for(int i1;in;i)if(!vis[headd[i]]){for(int jheadd[i];jj!t1;jnexxt[j])printf(%d ,j),vis[j]true;printf(\n);}
} View Code #includebits/stdc.h
using namespace std;
#define inf 2100000000
#define M 1000005
int to[M],nex[M],head[M],w[M],tot0,vis[M];
int nexxt[M],headd[M],lev[M],cur[M],sM-5,tM-4;
queueint q;
void add(int a,int b,int ww)
{to[tot]b; nex[tot]head[a]; head[a]tot; w[tot]ww;to[tot]a; nex[tot]head[b]; head[b]tot; w[tot]0;
}
bool bfs()
{memset(lev,-1,sizeof(lev));lev[s]0; q.push(s);while(!q.empty()){int uq.front(); q.pop();for(int ihead[u];i!-1;inex[i]){int vto[i];if(lev[v]-1 w[i]) lev[v]lev[u]1,q.push(v);}}return lev[t]!-1;
}
int dfs(int u,int flow)
{if(ut) return flow;int retflow;for(int ihead[u];i!-1;inex[i]){int vto[i];if(ret0) break;if(lev[v]lev[u]1w[i]0){int kdfs(v,min(ret,w[i]));nexxt[u1]v1;//记录一下这个球对应的下一个球是哪一个 因为存的时候*21了 所以要/2 不需要分奇偶讨论 ret-k; w[i]-k; w[i^1]k;}} return flow-ret;
}
int dinic()
{int ans0;while(bfs()){ansdfs(s,inf);} return ans;
}
int main()
{int n;scanf(%d,n);memset(head,-1,sizeof(head));int now0,zhu0;//柱子要从0开始因为第一次进去时一定最大流为 0 headd[1]1;while(zhun){now;add(s,now1,1); add(now1|1,t,1);
//now i*i 2*now 这样保证了i*i-now为正 且是小的数向大的数连边 for(int isqrt(now)1;i*inow*2;i)add((i*i-now)1,now1|1,1);int tmpdinic();if(!tmp) headd[zhu]now;//headd记录了每个柱子最下面的球是谁然后依次跳链表遍历整个柱子里面的球 }printf(%d\n,now-1);for(int i1;in;i)if(!vis[headd[i]]){//如果这个柱子的第一个球还没有被遍历 说明这个柱子还没被遍历 for(int jheadd[i];jj!t1;jnexxt[j])printf(%d ,j),vis[j]true;printf(\n);}
} 有注释的 最小割2题 洛谷P2774方格取数问题 题意 取了一个格子就不能取有公共边的格子求能取出的最大值。 分析 思路取了一种点 就不能取另外一种点 对于这样的限制关系 可以将对立的条件进行连边通过将边权设为inf的方式 限制不能同时选 也就是跑最大流(最小割 )最小割模板其实是要一部分的点向源点连边一部分向汇点连边的形式但是这道题我全部的点都向源汇点连了为什么没有错呢是因为有一个边权的限制在里面 使其可以跑对而下一道题骑士共存就不行了 #includebits/stdc.h
using namespace std;
#define inf 2100000000
#define N 20005
#define M 1000005
int to[M],head[N],nex[M],w[M],tot1,cnt0,sum0,lev[N],n,m;
//为了不与已有的点重复 nnn*m 注意扩展域的范围
int id[102][102],dx[5]{0,0,1,-1},dy[5]{1,-1,0,0},s0,t20001,nn10000,aa[102][102];
queueint q;
void add(int a,int b,int ww)
{to[tot]b; nex[tot]head[a]; head[a]tot; w[tot]ww;to[tot]a; nex[tot]head[b]; head[b]tot; w[tot]0;
}
bool bfs()
{memset(lev,-1,sizeof(lev));lev[s]0; q.push(s);while(!q.empty()){int uq.front(); q.pop();for(int ihead[u];i!-1;inex[i]){int vto[i];if(lev[v]-1w[i]0) lev[v]lev[u]1,q.push(v);}}return lev[t]!-1;
}
int dfs(int u,int flow)
{if(ut) return flow;int retflow;for(int ihead[u];i!-1;inex[i]){int vto[i];if(ret0) break;if(lev[v]lev[u]1w[i]0){int kdfs(v,min(ret,w[i]));ret-k; w[i]-k; w[i^1]k;}}return flow-ret;
} void dinic()
{int ans0;while(bfs()) ansdfs(s,inf);//printf(%d\n,ans);printf(%d\n,sum-ans/2);
}
int main()
{scanf(%d%d,m,n);memset(head,-1,sizeof(head));for(int i1;im;i)for(int j1;jn;j){scanf(%d,aa[i][j]);id[i][j]cnt;sumaa[i][j];}for(int i1;im;i)for(int j1;jn;j){add(s,id[i][j],aa[i][j]);add(id[i][j]nn,t,aa[i][j]);for(int k0;k3;k){int xdx[k]i,ydy[k]j;if(x1||xm||yn||y1) continue;add(id[i][j],id[x][y]nn,inf);}}dinic();
} View Code 洛谷P3355 骑士共存问题 题意 在一个位置放一个骑士其周围有八个位置都不能放还有障碍也不能放求最多能放多少个骑士 分析 与方格取数类似但一定要一部分连接源点一部分连汇点不能所以的点都连源汇点如果所有的都连了源汇点就会发现跑出来与s t相连的边都是满流的并没有起作用(因为边权值都为1)一部分连一部分不连就可以跑出正确的最小割了 一部分与另一部分的划分 是坐标之和的奇偶性 所以也叫奇偶建图为什么是坐标之和的奇偶呢 oxoxoxoxoxoxoxo如果我们将所有点分成O和X两种点我们可以发现同种点无法互相攻击那我们可以把所有点分成两个点集分别为O点的点集和X的点集然后在两个点集有某些点对无法全选 做法 先创一个源点和汇点 让源点到所有O点即横纵坐标加起来为奇数的点连一条容量为1的边 让所有X点即横纵坐标加起来为偶数的点到汇点连一条容量为1的边 再对无法同时选择的O点和X点让O点连一条到X点容量为inf的点 最后跑最大流设为最大流为x输出n∗n−m−x就好了 部分摘自洛谷第一篇题解 #includebits/stdc.h
using namespace std;
#define inf 2100000000
#define N 80005
#define M 1000005
int to[M],head[N],nex[M],w[M],tot1,cnt0,sum0,lev[N],n,m,cur[N];
int id[202][202],dx[8]{-2,-1,-2,-1,2,1,2,1},dy[8]{1,2,-1,-2,1,2,-1,-2};
int s0,t40001,nn40000,c[202][202];
queueint q;
void add(int a,int b,int ww)
{to[tot]b; nex[tot]head[a]; head[a]tot; w[tot]ww;to[tot]a; nex[tot]head[b]; head[b]tot; w[tot]0;
}
bool bfs()
{memset(lev,-1,sizeof(lev));for(int is;it;i) cur[i]head[i];lev[s]0; q.push(s);while(!q.empty()){int uq.front(); q.pop();for(int ihead[u];i!-1;inex[i]){int vto[i];if(lev[v]-1w[i]0) lev[v]lev[u]1,q.push(v);}}return lev[t]!-1;
}
int dfs(int u,int flow)
{if(ut) return flow;int retflow;for(int icur[u];i!-1;inex[i]){cur[u]i;int vto[i];if(ret0) break;if(lev[v]lev[u]1w[i]0){int kdfs(v,min(ret,w[i]));ret-k; w[i]-k; w[i^1]k;}}return flow-ret;
} void dinic()
{int ans0;while(bfs()) ansdfs(s,inf);
// printf(%d\n,ans);printf(%d\n,n*n-m-ans);
}
int main()
{int a,b;scanf(%d%d,n,m);memset(head,-1,sizeof(head));for(int i1;im;i) scanf(%d%d,a,b),c[a][b]1;for(int i1;in;i)for(int j1;jn;j){id[i][j]cnt;if(c[i][j]) continue;if((ij)1) add(s,id[i][j],1); //奇偶建图奇数点在左边 else { add(id[i][j],t,1); continue; }}for(int i1;in;i)for(int j1;jn;j){if(((ij)1)0||c[i][j]) continue;//障碍跳过 奇偶建图偶数点在右边 不进行连边 for(int k0;k7;k){int xdx[k]i,ydy[k]j;if(x1||y1||xn||yn||c[x][y]) continue;add(id[i][j],id[x][y],inf);}}dinic();
} View Code 费用流2题 洛谷P2045 方格取数加强版 题意现在从(1,1)出发,可以往右或者往下走,最后到达(n,n),每达到一格,把该格子的数取出来,该格子的数就变成0这样一共走K次,现在要求K次所达到的方格的数的和最大 反向边的费用置为-w的原因当反悔的时候 说明不获取这条边的费用 就走反向边 将原来获取的减去 建边先拆点拆成入点x和出点x x与x连费用为格子上的数 容量为 1的边 表示当第一次走的时候可以获取费用x与x再连一条费用为0 容量为 k-1的边 表示再走k-1次将不再获取费用x再向下和右的入点连费用为0 容量为 k的边表示走k次 不收获费用注意入点被别人连边 而出点向别人连边 #includebits/stdc.h
using namespace std;
#define N 5005
#define M 1000005
int to[M],head[N],nex[M],w[M],fl[M],tot1,flow[N],dis[N],vis[N],last[N],pre[N];//tot1!!
int s,t,nn2500,max_flow0,min_cost0,id[55][55];
queueint q;
void add(int a,int b,int ww,int ff)
{to[tot]b; nex[tot]head[a]; head[a]tot; w[tot]ww; fl[tot]ff;to[tot]a; nex[tot]head[b]; head[b]tot; w[tot]-ww; fl[tot]0;//反向边的费用置为负的
}
//spfa原理在残量网络上 将费用 w 视作边权 跑最短路
bool spfa()
{//费用流的前提都是保证最大流下再考虑费用
//而在此题里面 流的限制使得能够恰好取k次 memset(vis,0,sizeof(vis));//一定要记得都要memset memset(dis,0x7f7f7f,sizeof(dis));memset(flow,0x7f7f7f,sizeof(flow));dis[s]0; vis[s]1; q.push(s);while(!q.empty()){int uq.front(); q.pop(); vis[u]0;for(int ihead[u];i!-1;inex[i]){int vto[i];if(fl[i]0 dis[v]dis[u]w[i]){dis[v]dis[u]w[i];flow[v]min(flow[u],fl[i]);//flow[v]表示流到v这个点时 经过的流量限制是多少 last[v]i; pre[v]u;//last记录边的编号 pre记录点的前驱 if(!vis[v]) q.push(v),vis[v]1;}}}return dis[t]!2139062143;
}
void solve()
{while(spfa()){int nowt;//从终点往回跳 跳到起点 max_flowflow[t];min_costflow[t]*dis[t];//最小费用的定义 是容量与距离相乘 while(now!s){fl[last[now]]-flow[t];fl[last[now]^1]flow[t];nowpre[now];}}
}
int main()
{int x,n,k,cnt0;scanf(%d%d,n,k);memset(head,-1,sizeof(head));for(int i1;in;i)for(int j1;jn;j)id[i][j]cnt;s1; tcntnn;//注意这里的s t一定要设置成格子的左上方和右下方这两个点的入点和出点 //因为图中是没有额外向起点或终点连边的 for(int i1;in;i)for(int j1;jn;j){//printf(id:%d\n,id[i][j]);scanf(%d,x); x-x;//取负数将最大费用转化成最小费用 用spfa跑最短路 //将点转化成边拆点-拆成入点和出点-若要经过这个点 就必经入点与出点连接的这条边//第一次经过费用为原权值 多次经过则为0 经过k次的限制转化成边的容量 让网络流限制其恰好经过k次 add(id[i][j],id[i][j]nn,x,1); add(id[i][j],id[i][j]nn,0,k-1);if(in) add(id[i][j]nn,id[i1][j],0,k);//出边连向其它点 其它点连向入边 if(jn) add(id[i][j]nn,id[i][j1],0,k);}solve();printf(%d\n,-min_cost);
}
/*
3 2
1 2 3
0 2 1
1 4 2
*/ View Code 洛谷P1251 餐巾计划问题 关键是如何建边 然后跑最小费用最大流。 建边方法将一个点视作餐厅的一天拆成两部分早上和晚上。 s视作纸巾的来源t视作纸巾的去处。下面开始连边。 每天晚上花费0得到早上用过的纸巾s - in (0) 每天早上花费0用掉当天所需的纸巾i -t (0) 每天早上花费p重新买纸巾s -i (p) 每天晚上的脏纸巾可以花费快洗的费用送到后m天使用in - im kf 慢洗同理 每天用过的脏纸巾不一定今天洗可以连向每天晚上洗in - in1 (0) #includebits/stdc.h
using namespace std;
#define N 4005
#define M 1000005
#define ll long long
#define inf 2100000000
int to[M],nex[M],head[N],w[M],fl[M],vis[N],flow[N],last[N],pre[N];
int tot1,s0,t4001;
ll dis[N],min_cost0;
queueint q;
void add(int a,int b,int ww,int ff)
{to[tot]b; nex[tot]head[a]; head[a]tot; w[tot]ww; fl[tot]ff;to[tot]a; nex[tot]head[b]; head[b]tot; w[tot]-ww; fl[tot]0;
}
bool spfa()
{memset(vis,0,sizeof(vis));memset(dis,0x7f7f7f,sizeof(dis));//注意int的 0x7f7f7f和 long long的不一样 memset(flow,0x7f7f7f,sizeof(flow));dis[s]0; q.push(s); vis[s]1;while(!q.empty()){int uq.front(); q.pop(); vis[u]0;//!!!一定要加 否则就打了个假的spfa for(int ihead[u];i!-1;inex[i]){int vto[i];if(fl[i]0 dis[v]dis[u]w[i]){dis[v]dis[u]w[i];flow[v]min(fl[i],flow[u]);last[v]i; pre[v]u;if(!vis[v]) q.push(v),vis[v]1;}}}return dis[t]!9187201950435737471;
}
void solve()
{while(spfa()){int nowt;min_costdis[t]*flow[t];while(now!s){fl[last[now]]-flow[t];fl[last[now]^1]flow[t];nowpre[now];}}
}
int main()
{int n,p,m,mf,k,kf,x;scanf(%d,n);memset(head,-1,sizeof(head));//i代表每天早上 in代表每天晚上 //用掉纸巾向 t连边 得到被s连边 for(int i1;in;i){scanf(%d,x);add(i,t,0,x); add(s,in,0,x);//每天早上用掉 x张纸巾 每天晚上得到 x张脏的纸巾 } scanf(%d%d%d%d%d,p,k,kf,m,mf);for(int i1;in;i){if(i1n) add(in,i1n,0,inf);//留到第二天晚上洗 if(imn) add(in,im,mf,inf);//慢洗今天晚上送去洗 m天后的早上得到 可以送去任意条 if(ikn) add(in,ik,kf,inf);//同理 add(s,i,p,inf);//每天早上可以从s那里通过p的代价重新购买 }solve();printf(%lld\n,min_cost);
}
/*
3
1 7 5
11 2 2 3 12 1 7
11 1 3 3 1
*/ View Code 我写错的地方spfa可以重复入队所以出队后应该清除标记 最小路径覆盖1题 洛谷P2764 最小路径覆盖问题 题意 求最小路径覆盖条数并输出方案。 最小路径覆盖 n个点的无向图最多需要n条路径覆盖每个点覆盖它自己。但其实可以一条路径的尾节点与另一条路径的首节点相连合并成一条路径。这样每合并一次路径条数就会减少一条。于是就将问题转化成了最多能合并多少条路径。然后开始建图s - i , in - t (1) 。然后原图中有边的相互连边最后跑最大流即可。 ansn-最大流 方案输出 在dfs里面记录一个点下一个点是谁在输出方案的时候像跳链表一样依次输出。但要注意的是每次要找到一条路径的端点通过打vis标记才能正确输出。 两种dfs写法不一样会导致答案也不一样 #includebits/stdc.h
using namespace std;
#define N 305
#define M 1000005
int ans0,tot1,n,m,s0,t301;
int to[M],head[N],nex[M],w[M],lev[N],cur[N],vis[N],nextt[N],fl[N];
queueint q;
void add(int a,int b,int ww)
{to[tot]b; nex[tot]head[a]; w[tot]ww; head[a]tot;to[tot]a; nex[tot]head[b]; w[tot]0; head[b]tot;
}
bool bfs()
{memset(lev,-1,sizeof(lev));for(int is;it;i) cur[i]head[i];lev[s]0; q.push(s);while(!q.empty()){int uq.front(); q.pop();for(int ihead[u];i!-1;inex[i]){int vto[i];if(lev[v]-1w[i]0) lev[v]lev[u]1,q.push(v);}}return lev[t]!-1;
}
int dfs( int now, int flow)
{if(nowt)return flow;for(int icur[now];i;inex[i]){cur[now]i;int qwto[i];if(w[i]0lev[qw]lev[now]1){int kkdfs(qw,min(flow,w[i]));if(kk0){nextt[now]qw;//记录一个点下一个点是谁 便于方案输出 if(now!s) vis[qw-n]1;//打标记找到一条路径的起点 最后没有被标记的就是起点 w[i]-kk,w[i^1]kk;return kk;}}}return 0;
}
/*int dfs(int u,int flow)另一种写法是错的。。。
{if(ut) return flow;int retflow;for(int icur[u];i!-1;inex[i]){cur[u]i;int vto[i];if(ret0) break;if(w[i]0lev[v]lev[u]1){int kdfs(v,min(ret,w[i]));if(u!s) vis[v-n]true;//!!nextt[u]v;ret-k; w[i]-k; w[i^1]k;}}return flow-ret;
}*/
void dinic()
{while(bfs()) ansdfs(s,2100000000);
}
int main()
{scanf(%d%d,n,m);memset(head,-1,sizeof(head));for(int i1;in;i) add(s,i,1),add(in,t,1);int a,b;for(int i1;im;i){scanf(%d%d,a,b);add(a,bn,1);}dinic();for(int i1;in;i)if(!vis[i]){int nowi;printf(%d ,now);while(nextt[now]nextt[now]!t){printf(%d ,nextt[now]-n);nownextt[now]-n;}printf(\n);} printf(%d\n,n-ans);
}
/*
11 9
1 2
1 3
1 4
2 5
3 6
4 7
6 9
7 10
8 114 3
4 1
1 2
2 3
*/ View Code 转载于:https://www.cnblogs.com/mowanying/p/11341451.html
