//题意:给定一个有向网络,每条边均有一个容量。问是否存在一个从点1到点N,流量为C的流。 //如果不存在,是否可以恰好修改一条弧的容量,使得存在这样的流? // //分析:先求一次最大流,如果流量至少为C,则直接输出possible,否则需要修改的弧一定是最小割里的弧。 //依次把这些弧的容量增加到C,然后再求最大流,看最大流量是否至少为C即可。 //很可惜,这样写出来的程序会超时,还需要加两个重要的优化。第一个优化是求完最大流后把流量留着,以 //后每次在它的基础上增广,第二个优化是每次没必要求出最大流,增广到流量至少为C时就停下来 #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<algorithm> using namespace std; const int maxn = 100 + 10; const int INF = 1000000000; struct Edge { int from, to, cap, flow; }; bool operator < (const Edge& a, const Edge& b) { return a.from < b.from || (a.from == b.from && a.to < b.to); } struct ISAP { int n, m, s, t; vector<Edge> edges; vector<int> G[maxn]; // 邻接表,G[i][j]表示结点i的第j条边在e数组中的序号 bool vis[maxn]; // BFS使用 int d[maxn]; // 从起点到i的距离 int cur[maxn]; // 当前弧指针 int p[maxn]; // 可增广路上的上一条弧 int num[maxn]; // 距离标号计数 void AddEdge(int from, int to, int cap) {//添加边 edges.push_back((Edge){from, to, cap, 0});//注意:有的编译器不支持这里 edges.push_back((Edge){to, from, 0, 0}); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BFS() { memset(vis, 0, sizeof(vis)); queue<int> Q; Q.push(t); vis[t] = 1; d[t] = 0; while(!Q.empty()) { int x = Q.front(); Q.pop(); for(int i = 0; i < G[x].size(); i++) { Edge& e = edges[G[x][i]^1]; if(!vis[e.from] && e.cap > e.flow) { vis[e.from] = 1; d[e.from] = d[x] + 1; Q.push(e.from); } } } return vis[s]; } void ClearAll(int n) {//初始化 this->n = n; for(int i = 0; i < n; i++) G[i].clear(); edges.clear(); } void ClearFlow() {//清空流量 for(int i = 0; i < edges.size(); i++) edges[i].flow = 0; } int Augment() { int x = t, a = INF; while(x != s) { Edge& e = edges[p[x]]; a = min(a, e.cap-e.flow); x = edges[p[x]].from; } x = t; while(x != s) { edges[p[x]].flow += a; edges[p[x]^1].flow -= a; x = edges[p[x]].from; } return a; } int Maxflow(int s, int t, int need) {//如果达到need,就结束,达不到,就返回最大 this->s = s; this->t = t; int flow = 0; BFS(); memset(num, 0, sizeof(num)); for(int i = 0; i < n; i++) num[d[i]]++; int x = s; memset(cur, 0, sizeof(cur)); while(d[s] < n) { if(x == t) { flow += Augment(); if(flow >= need) return flow; x = s; } int ok = 0; for(int i = cur[x]; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if(e.cap > e.flow && d[x] == d[e.to] + 1) { // Advance ok = 1; p[e.to] = G[x][i]; cur[x] = i; // 注意 x = e.to; break; } } if(!ok) { // Retreat int m = n-1; // 初值注意 for(int i = 0; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if(e.cap > e.flow) m = min(m, d[e.to]); } if(--num[d[x]] == 0) break; num[d[x] = m+1]++; cur[x] = 0; // 注意 if(x != s) x = edges[p[x]].from; } } return flow; } vector<int> Mincut() { //可以找出瓶颈路,需要先调用Maxflow BFS(); vector<int> ans; for(int i = 0; i < edges.size(); i++) { Edge& e = edges[i]; if(!vis[e.from] && vis[e.to] && e.cap > 0) ans.push_back(i); } return ans; } void Reduce() {//优化部分,把已经用的流量删除掉,再算需要增加哪条路的流量 for(int i = 0; i < edges.size(); i++) edges[i].cap -= edges[i].flow; } void print() {//测试用 printf("Graph:\n"); for(int i = 0; i < edges.size(); i++) printf("%d->%d, %d, %d\n", edges[i].from, edges[i].to , edges[i].cap, edges[i].flow); } }; ISAP g; int main() { int n, e, c, kase = 0; while(scanf("%d%d%d", &n, &e, &c) == 3 && n) { g.ClearAll(n); while(e--) { int b1, b2, fp; scanf("%d%d%d", &b1, &b2, &fp); g.AddEdge(b1-1, b2-1, fp);//算法从0开始,如果是双向的,要看做两个单向的 } int flow = g.Maxflow(0, n-1, INF);//计算从0到n-1的最大流 printf("Case %d: ", ++kase); if(flow >= c) printf("possible\n"); else { vector<int> cut = g.Mincut(); g.Reduce(); vector<Edge> ans; for(int i = 0; i < cut.size(); i++) { Edge& e = g.edges[cut[i]]; e.cap = c; g.ClearFlow(); if(flow + g.Maxflow(0, n-1, c-flow) >= c) ans.push_back(e); e.cap = 0;//把修改后能达到c的路都保存起来 } if(ans.empty()) printf("not possible\n"); else { sort(ans.begin(), ans.end()); printf("possible option:(%d,%d)", ans[0].from+1, ans[0].to+1); for(int i = 1; i < ans.size(); i++) printf(",(%d,%d)", ans[i].from+1, ans[i].to+1); printf("\n"); } } } return 0; }
相关推荐
isap模板
用于计算最大网络流的经典的ISAP算法,代码自带例子,边权支持double类型。
这里面的内容是个PPT,介绍的很好,如果你想更加的清楚 最大流的原理,这是个不错的选择
原题为USACO 草地排水 模板,网络流,最大流,ISAP算法 虽然可能写的不怎么好看但是带一些注释,应该可以看懂吧。
图论- 网络流- 最大流- SAP 算法与 ISAP 算法.rar
网络流的isap图片集(当ppt看),多看看,在参考点论文就能入门了》。。
SyncMOS ISAP Delphi Sample Code
SyncMOS ISAP User Menu
用C++实现的3种最大流算法。CS(Capacity-Scaling Algorithm)、SAP(Shortest Augmenting Path Algorithm)、ISAP(Improved Shortest Augmenting Path Algorithm)。
北京恒光综合接入设备iSAP2000升级文件及配置指导书,使用请注意查看版本
网络流算法,自己写的实现最大流问题的好方法,是用邻接表实现的ISAP,网上可是很少的哟
iSAP MetaWeb中文文档.rar
2.2 网络流ISAP算法……………………………………………….(6) 3.1 最小生成树Kruskal算法………………………………………(9) 3.2 最小生成树prim算法…………………………………………..(11) 3.3 最优生成树……...
1 字符串处理 5 1.1 KMP . . . . . . . . ....1.2 e-KMP ....1.3 Manacher ....1.4 AC 自动机 ....1.5 后缀数组 ....1.5.1 DA ....1.5.2 DC3 ....1.6 后缀自动机 ....1.6.1 基本函数 ....1.6.2 例题 ....1.7 字符串 hash ....2.1 素数 ....
ERP系统信息化资料:ISAP专业培训教材T战略2.ppt
非常好的最大流入门!详解了EK与ISAP,OIer, ACMer 入门必备!
ERP系统信息化资料:ISAP专业培训教材ntro to ABAP - Chapter 10.ppt
ERP系统信息化资料:ISAP专业培训教材ntro to ABAP - Chapter 03.ppt
为了提高资源利用率且降低干扰,通过运用ISAP算法来完成合理的资源分配,从而实现D2D对与频谱资源之间的一对多的复用关系;同时,在满足各用户不同QoS需求的前提下,可将干扰有效抑制在合理的范围内。通过仿真实验...
网络流有两种写法,dinic和sap(isap) 本人太弱了,只会dinic 目的 首先,明确网络流是干什么的 给定指定的一个有向图,其中有两个特殊的点源S(Sources)和汇T(Sinks),每条边有指定的容量(Capacity),求满足条件的从...