当前位置: 首页 > news >正文

网站怎么做长尾关键词宣传片制作公司排行

网站怎么做长尾关键词,宣传片制作公司排行,wordpress xiu主题5.4,国内html5网站欣赏题目来源 P3376 【模板】网络最大流P2756 飞行员配对方案问题P3381 【模板】最小费用最大流最大流 最大流问题是网络流的经典类型之一#xff0c;用处广泛#xff0c;个人认为网络流问题最具特点的操作就是建反向边#xff0c;这样相当于给了反悔的机会#xff0c;不断地求… 题目来源 P3376 【模板】网络最大流P2756 飞行员配对方案问题P3381 【模板】最小费用最大流最大流 最大流问题是网络流的经典类型之一用处广泛个人认为网络流问题最具特点的操作就是建反向边这样相当于给了反悔的机会不断地求增广路的最终得到最大流 #includeiostream #includecstdio #includealgorithm #includecstring #includequeue #includestring #includefstream #includevector #includestack #include map #include iomanip #define bug cout ********** endl #define show(x,y) cout[x,y] //#define LOCAL 1; using namespace std; typedef long long ll; const int inf 0x3f3f3f3f; const ll mod 1e6 3; const int Max 1e5 10;struct Edge {int to, next, flow; //flow记录这条边当前的边残量 }edge[Max 1];int n, m, s, t; int head[Max], tot; bool vis[Max];void init() {memset(head, -1, sizeof(head));tot 0; }void add(int u, int v, int flow) {edge[tot].to v;edge[tot].flow flow;edge[tot].next head[u];head[u] tot; }//向图中增加一条容量为exp的边增广路 int dfs(int u,int exp) {if (u t) return exp; //到达汇点当前水量全部注入vis[u] true; //表示已经到了过了for(int i head[u] ; i ! -1 ;i edge[i].next){int v edge[i].to;if(!vis[v] edge[i].flow 0){int flow dfs(v, min(exp, edge[i].flow));if(flow 0) //形成了增广路{edge[i].flow - flow;edge[i ^ 1].flow flow;return flow;}}}return 0; //无法形成增广路的情况 }//求最大流 int max_flow() {int flow 0;while(true){memset(vis, 0, sizeof(vis));int part_flow dfs(s, inf);if (part_flow 0) return flow;flow part_flow;} }int main() { #ifdef LOCALfreopen(input.txt, r, stdin);freopen(output.txt, w, stdout); #endifwhile (scanf(%d%d%d%d, n, m, s, t) ! EOF){init();for (int i 1, u, v, flow;i m; i){scanf(%d%d%d, u, v, flow);add(u, v, flow);add(v, u, 0);}printf(%d\n, max_flow());}return 0; } 最简单算法-Ford-Fulkerson #includeiostream #includecstdio #includealgorithm #includecstring #includequeue #includestring #includefstream #includevector #includestack #include map #include iomanip #define bug cout ********** endl #define show(x,y) [x,y] //#define LOCAL 1; using namespace std; typedef long long ll; const int inf 0x3f3f3f3f; const ll mod 1e6 3; const int Max 1e5 10;struct Edge {int to, next, flow; //flow记录这条边当前的边残量 }edge[Max 1];int n, m, s, t; int head[Max], tot; int dis[Max];void init() {memset(head, -1, sizeof(head));tot 0; }void add(int u, int v, int flow) {edge[tot].to v;edge[tot].flow flow;edge[tot].next head[u];head[u] tot; }bool bfs() //判断图是否连通 {queueintq;memset(dis, -1, sizeof(dis));dis[s] 0;q.push(s);while (!q.empty()){int u q.front();q.pop();for (int i head[u]; i ! -1; i edge[i].next){int v edge[i].to;if (dis[v] -1 edge[i].flow 0) //可以借助边i到达新的结点{dis[v] dis[u] 1; //求顶点到源点的距离编号q.push(v);}}}return dis[t] ! -1; //确认是否连通 }int dfs(int u, int flow_in) {if (u t) return flow_in;int flow_out 0; //记录这一点实际流出的流量for (int i head[u]; i ! -1;i edge[i].next){int v edge[i].to;if (dis[v] dis[u] 1 edge[i].flow 0){int flow_part dfs(v, min(flow_in, edge[i].flow));if (flow_part 0)continue; //无法形成增广路flow_in - flow_part; //流出了一部分剩余可分配流入就减少了flow_out flow_part; //记录这一点最大的流出 edge[i].flow - flow_part;edge[i ^ 1].flow flow_part; //减少增广路上边的容量增加其反向边的容量if (flow_in 0)break;}}return flow_out; }int max_flow() {int sum 0;while (bfs()){sum dfs(s, inf);}return sum; }int main() { #ifdef LOCALfreopen(input.txt, r, stdin);freopen(output.txt, w, stdout); #endifwhile (scanf(%d%d%d%d, n, m, s, t) ! EOF){init();for (int i 1, u, v, flow;i m; i){scanf(%d%d%d, u, v, flow);add(u, v, flow);add(v, u, 0);}printf(%d\n, max_flow());}return 0; } 常用且高效的算法-Dinic  二分图匹配 要解决这类问题我们需要先了解什么是二分图 二分图一个图中的所有顶点可以分为两个集合 V,K ,其实两个集合内部的点彼此之间无边如下图所示蓝色的点和红色的点分属于两个集合V,K) 然后我们回到这个题目上来这个题目求的是最大可出战人数实际上就是在二分图中找到两个集合中的最大匹配数这类问题我们称之为二分图最大匹配数问题 属于网络流经典题目之一下面说明一下建图的过程 1由源点向集合V中每个点建一条容量为1的边 2对于VK集合之间存在的边ev 为V中的点,k为K中的点我们建一条容量为1的边方向为 v -- k  3由K中每个点向汇点建一条容量为1的边 当我们将图建好了后我们求这个图的最大流这个最大流即为二分图最大匹配数下面展示一下建成的图(S代表源点T代表汇点蓝色的边代表容量为1的边 #includeiostream #includecstdio #includealgorithm #includecstring #includequeue #includestring #includefstream #includevector #includestack #include map #include iomanip #define bug cout ********** endl #define show(x,y) cout[x,y] //#define LOCAL 1; using namespace std; typedef long long ll; const int inf 0x3f3f3f3f; const ll mod 1e6 3; const int Max 1e6 10;struct Edge {int to, next, flow; }edge[Max 1];;int n, m, a, b, s, t; int head[Max], tot; int dis[Max]; int ans; bool vis[Max];void init() {memset(head, -1, sizeof(head));tot 0;ans 0; }void add(int u, int v, int flow) {edge[tot].to v;edge[tot].flow flow;edge[tot].next head[u];head[u] tot; }bool bfs() {memset(dis, -1, sizeof(dis));dis[s] 0;queueintq;q.push(s);while (!q.empty()){int u q.front();q.pop();for (int i head[u]; i ! -1;i edge[i].next){int v edge[i].to;if (dis[v] -1 edge[i].flow 0){dis[v] dis[u] 1;if (v t) return true;q.push(v);}}}return false; }int dfs(int u, int flow_in) {if (u t) return flow_in;int flow_out 0;for (int i head[u]; i ! -1;i edge[i].next){int v edge[i].to;if (dis[v] dis[u] 1 edge[i].flow 0){int flow_part dfs(v, min(flow_in, edge[i].flow));if (flow_part 0) continue;flow_in - flow_part;flow_out flow_part;edge[i].flow - flow_part;edge[i ^ 1].flow flow_part;if (flow_in 0)break;}}return flow_out; }int max_val() {int sum 0;while (bfs()){sum dfs(s, inf);}return sum; }int main() { #ifdef LOCALfreopen(input.txt, r, stdin);freopen(output.txt, w, stdout); #endifwhile (scanf(%d%d, m, n) ! EOF){init();s 0, t n 1;for (int i 1;i m;i){add(s, i, 1);add(i, s, 0); //由源点向外籍飞行员建边}for (int i m 1; i n;i){add(i, t, 1);add(t, i, 0);}while (scanf(%d%d, a, b) ! EOF a ! -1 b ! -1){add(a, b, 1);add(b, a, 0);}printf(%d\n, max_val());for (int u 1;u m;u){for (int i head[u]; i ! -1;i edge[i].next){if (edge[i].flow 0 edge[i].to ! s edge[i].to ! t){printf(%d %d\n, u, edge[i].to);}}}}return 0; } 飞行员配对方案-Dinic  最小费用最大流 这类题目相比于最大流问题新增了每天边单位流量的价格问在最大流的情况下求出最小的费用。 这类题目和最大流很想不过也有不小区别对于这类问题我们为每条边建的反边的价格是每天边的相反数如图 然后我们的算法也不再是Dinic算法了而是用spfa或者dijkstra #pragma GCC optimize(2) #includeiostream #includecstdio #includealgorithm #includecstring #includequeue #includestring #includefstream #includevector #includestack #include map #include iomanip #define bug cout ********** endl #define show(x,y) cout[x,y] #define LOCAL 1; using namespace std; typedef long long ll; const int inf 0x3f3f3f3f; const ll mod 1e9 7; const int Max 5e3 10;struct Edge {int to, rev; //rev记录反向边int flow, cost;; };int n, m, k; vectorEdgeedge[Max 1]; int h[Max]; //每个结点的势 int dis[Max]; int pre_node[Max], pre_edge[Max]; //前驱结点和对应边void add(int u, int v, int flow, int cost) {edge[u].push_back({ v,(int)edge[v].size(),flow,cost });edge[v].push_back({ u,(int)edge[u].size() - 1,0,-cost }); }void min_cost_flow(int s, int t, int min_cost, int max_flow) {fill(h 1, h 1 n, 0);min_cost max_flow 0;int tot inf; //源点流量无限while (tot 0){priority_queuepairint, int, vectorpairint, int , greaterpairint, int q;memset(dis, inf, sizeof(dis));dis[s] 0;q.push({ 0,s });while (!q.empty()){int u q.top().second;int dist q.top().first;q.pop();if (dis[u] dist)continue; //当前的距离不是最近距离for (int i 0;i edge[u].size(); i){Edge e edge[u][i];if (edge[u][i].flow 0 dis[e.to] dis[u] e.cost h[u] - h[e.to]){dis[e.to] dis[u] e.cost h[u] - h[e.to];pre_node[e.to] u;pre_edge[e.to] i;q.push({ dis[e.to],e.to });}}}if (dis[t] inf)break; //无法增广了就是找到答案了for (int i 1;i n;i) h[i] dis[i];int flow tot; //求这一增广路径的流量for (int i t; i ! s; i pre_node[i])flow min(flow, edge[pre_node[i]][pre_edge[i]].flow);for (int i t; i ! s; i pre_node[i]){Edge e edge[pre_node[i]][pre_edge[i]];e.flow - flow;edge[i][e.rev].flow flow;}tot - flow;max_flow flow;min_cost flow * h[t];} }int main() { #ifdef LOCAL//freopen(input.txt, r, stdin);//freopen(output.txt, w, stdout); #endifint s, t;while (scanf(%d%d%d%d, n, m, s, t) ! EOF){for (int i 1, u, v, flow, cost;i m;i){scanf(%d%d%d%d, u, v, flow, cost);add(u, v, flow, cost);}int min_cost, max_flow;min_cost_flow(s, t, min_cost, max_flow);printf(%d %d\n, max_flow, min_cost);}return 0; } 无负环图中可用的算法-dijkstra这里给出的是可以适用于有负环的 #includeiostream #includecstdio #includealgorithm #includecstring #includequeue #includestring #includefstream #includevector #includestack #include map #include iomanip #define bug cout ********** endl #define show(x,y) cout[x,y] //#define LOCAL 1; using namespace std; typedef long long ll; const int inf 0x3f3f3f3f; const ll mod 1e9 7; const int Max 1e5 10;struct Edge {int to, next;int flow, cost; }edge[Max 1];int n, m, s, t; int head[Max], tot; int dis[Max]; int pre[Max]; //记录增广路径此点的前一天边 bool vis[Max];void init() {memset(head, -1, sizeof(head));tot 0; }void add(int u, int v, int flow, int cost) {edge[tot].to v;edge[tot].flow flow;edge[tot].cost cost;edge[tot].next head[u];head[u] tot;edge[tot].to u;edge[tot].flow 0;edge[tot].cost -cost;edge[tot].next head[v];head[v] tot; }bool spfa(int s, int t) {memset(dis, inf, sizeof(dis));memset(vis, 0, sizeof(vis));memset(pre, -1, sizeof(pre));queueintq;q.push(s);dis[s] 0;vis[s] true;while (!q.empty()){int u q.front();q.pop();vis[u] false;for (int i head[u]; i ! -1; i edge[i].next){int v edge[i].to;if (edge[i].flow 0 dis[v] dis[u] edge[i].cost){dis[v] dis[u] edge[i].cost;pre[v] i;if (!vis[v]){vis[v] true;q.push(v);}}}}return pre[t] ! -1; }void min_cost_max_flow(int s, int t, int max_flow, int min_cost) {max_flow 0;min_cost 0;while (spfa(s, t)){int flow inf;for (int i pre[t]; i ! -1; i pre[edge[i ^ 1].to]) //沿增广路回溯edge[i^1]即为其反边{flow min(flow, edge[i].flow);}for (int i pre[t]; i ! -1; i pre[edge[i ^ 1].to]){edge[i].flow - flow;edge[i ^ 1].flow flow;min_cost flow * edge[i].cost;}max_flow flow;} }int main() { #ifdef LOCALfreopen(input.txt, r, stdin);freopen(output.txt, w, stdout); #endifwhile (scanf(%d%d%d%d, n, m, s, t) ! EOF){init();for (int i 1, u, v, flow, cost;i m;i){scanf(%d%d%d%d, u, v, flow, cost);add(u, v, flow, cost);}int max_flow 0, min_cost 0;min_cost_max_flow(s, t, max_flow, min_cost);printf(%d %d\n, max_flow, min_cost);}return 0; } 常用且比较高效的算法-spfa   转载于:https://www.cnblogs.com/winter-bamboo/p/11330082.html
http://www.huolong8.cn/news/61990/

相关文章:

  • 合肥寒假兼职工网站建设iis网站目录权限
  • 做网站着用什么电脑网络运营者应当对其收集的用户信息严格保密
  • 中国十大热门网站排名wordpress 摄影工作室主题
  • 建设公司官方网站个人社保缴费记录查询
  • 上海涛飞专业网站建设wordpress 小工具
  • 人流医院网站建设话费充值代理平台
  • 网站后台生成文章很慢基于php网站开发的参考文献
  • 建设网站石家庄博客seo优化技术
  • 如何使用好单库选品库做网站提供深圳网站制作公司
  • 网站开发 技术路线做集团网站一年多少钱
  • 长安网站建设多少钱百度百姓网
  • 后端开发网站做一些什么建网站大概多少费用
  • 静态网站可以申请域名吗如何自己做微信小程序
  • 网站设计参考网站互联网10大厂
  • 网站设计的机构wordpress添加分享
  • 自己切片做网站wordpress concise
  • 做八闽最好的中学网站南阳网站建设seo
  • 菏泽市建设局网站电话号码外网建筑设计网站
  • 视频分享网站怎么做的东莞个人免费建网站
  • 创建站点的方法做网站发布
  • 互联网做网站的话术南京营销型网站建设公司
  • 未来做哪些网站致富临海app开发
  • 做网站百度关键排名个人可以做几个网站
  • 惠州建设局网站首页炒股软件下载
  • 足球直播网站怎么做的外贸网站开发推广
  • 上饶网站建设公司建物流网站
  • 东莞网站建设 南城石佳东莞站福公司工资
  • dw做的网站怎么做后台天堂2免费服务器
  • 天翼电子商务有限公司seo服务销售招聘
  • 杭州做企业网站的公司在线crm什么软件好