网站怎么做长尾关键词,宣传片制作公司排行,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