关键割边就是增加某条边的容量,使得网络的最大流增加。
步骤:
1. 求最大流,得到残余网络。
2. 在残余图上从s点出发dfs,得到割边(a,b)。
3. 从t点出发反向dfs,得到所有能到达t的点。
4. 对于某条割边(a,b),若b能到达t,则该边为关键割边。(因为从s到t的路径上只有这一条割边,增加这条割边,肯定可以增加流量)。
例:POJ3024
题意:找关键割边数量。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x7fffffff;
const int maxv = 505;
const int maxe = 5005*2;
int n,m;
int col[maxv];
bool vis[maxv];
//
struct Edge
{
int v;
int next;
int flow;
};
Edge e[maxe];
int head[maxv],edgeNum;
int now[maxv],d[maxv],vh[maxv],pre[maxv],preh[maxv];
void addEdge(int a,int b,int c)
{
e[edgeNum].v = b;
e[edgeNum].flow = c;
e[edgeNum].next = head[a];
head[a] = edgeNum++;
e[edgeNum].v = a;
e[edgeNum].flow = 0;
e[edgeNum].next = head[b];
head[b] = edgeNum++;
}
void Init()
{
edgeNum = 0;
memset(head,-1,sizeof(head));
memset(d,0,sizeof(d));
}
int sap(int s,int t,int n) //源点,汇点,结点总数
{
int i,x,y;
int f,ans = 0;
for(i = 0; i < n; i++)
now[i] = head[i];
vh[0] = n;
x = s;
while(d[s] < n)
{
for(i = now[x]; i != -1; i = e[i].next)
if(e[i].flow > 0 && d[y=e[i].v] + 1 == d[x])
break;
if(i != -1)
{
now[x] = preh[y] = i;
pre[y] = x;
if((x=y) == t)
{
for(f = INF,i=t; i != s; i = pre[i])
if(e[preh[i]].flow < f)
f = e[preh[i]].flow;
ans += f;
do
{
e[preh[x]].flow -= f;
e[preh[x]^1].flow += f;
x = pre[x];
}while(x!=s);
}
}
else
{
if(!--vh[d[x]])
break;
d[x] = n;
for(i=now[x]=head[x]; i != -1; i = e[i].next)
{
if(e[i].flow > 0 && d[x] > d[e[i].v] + 1)
{
now[x] = i;
d[x] = d[e[i].v] + 1;
}
}
++vh[d[x]];
if(x != s)
x = pre[x];
}
}
return ans;
}
void minmGe(int x)
{
col[x] = 1;
for(int i = head[x]; i != -1; i = e[i].next)
{
int to = e[i].v;
if(e[i].flow > 0 && !col[to])
minmGe(to);
}
}
//
void dfs(int now)
{
vis[now] = true;
for(int i = head[now]; i != -1; i = e[i].next)
{
if(i%2==0)
continue;
int to = e[i].v;
if(e[i^1].flow>0&&!vis[to])
dfs(to);
}
}
int main()
{
int i,j;
int from,to,c;
Init();
memset(col,0,sizeof(col));
memset(vis,0,sizeof(vis));
scanf("%d %d",&n,&m);
for(i = 0; i < m; i++)
{
scanf("%d %d %d",&from,&to,&c);
addEdge(from,to,c);
}
sap(0,n-1,n);
minmGe(0);
int result = 0;
dfs(n-1);
for(i = 0; i < n; i++)
{
if(!col[i])
continue;
for(j = head[i]; j != -1; j = e[j].next)
{
int to = e[j].v;
if(j%2==0 && col[to]==0 && vis[to])
result++;
}
}
printf("%d\n",result++);
return 0;
}
分享到:
相关推荐
1.1.1.5 关键边 1.1.1.6 最大流判定 1.1.1.7 拆点 1.1.1.8 建图实战 1.1.2 最小割 1.1.2.1 算法模板 1.1.2.2 直接应用 1.1.2.3 最大权闭合图 1.1.2.4 最大密度子图 1.1.2.5 最小点权覆盖集 1.1.2.6 最大点权独立集 ...
无向图关键边(dfs邻接阵形式) 无向图关键点(dfs邻接阵形式) 无向图块(bfs邻接阵形式) 无向图连通分支(bfs邻接阵形式) 无向图连通分支(dfs邻接阵形式) 有向图强连通分支(bfs邻接阵形式) 有向图强连通分支(dfs...
无向图关键边(dfs邻接阵形式) 无向图关键点(dfs邻接阵形式) 无向图块(bfs邻接阵形式) 无向图连通分支(bfs邻接阵形式) 无向图连通分支(dfs邻接阵形式) 有向图强连通分支(bfs邻接阵形式) 有向图强连通分支(dfs...
无向图关键边(dfs邻接阵形式) 无向图关键点(dfs邻接阵形式) 无向图块(bfs邻接阵形式) 无向图连通分支(bfs邻接阵形式) 无向图连通分支(dfs邻接阵形式) 有向图强连通分支(bfs邻接阵形式) 有向图强连通分支(dfs...
7.2 无向图关键边(dfs邻接阵) 78 7.3 无向图的块(bfs邻接阵) 79 7.4 无向图连通分支(dfs/bfs邻接阵) 80 7.5 有向图强连通分支(dfs/bfs邻接阵) 81 7.6 有向图最小点基(邻接阵) 828、 图论—匹配 83 8.1 二分图最大...
7.2 无向图关键边(dfs邻接阵) 78 7.3 无向图的块(bfs邻接阵) 79 7.4 无向图连通分支(dfs/bfs邻接阵) 80 7.5 有向图强连通分支(dfs/bfs邻接阵) 81 7.6 有向图最小点基(邻接阵) 82 8、 图论—匹配 83 8.1 二分图最大...
1. 无向图关键边(dfs邻接阵形式) 2. 无向图关键点(dfs邻接阵形式) 3. 无向图块(bfs邻接阵形式) 4. 无向图连通分支(bfs邻接阵形式) 5. 无向图连通分支(dfs邻接阵形式) 6. 有向图强连通分支(bfs邻接阵形式) 7. ...
第4节 关键道路——图的割边 234 第5节 我要做月老——二分图zui大匹配 237 第9章 还能更好吗——微软亚洲研究院面试 243 啊哈算法 目 录 第1章 编程改变思维 1 第1节 为什么要学习编程 1 第2节 本书是讲...
1. 无向图关键边(dfs邻接阵形式) 41 2. 无向图关键点(dfs邻接阵形式) 42 3. 无向图块(bfs邻接阵形式) 43 4. 无向图连通分支(bfs邻接阵形式) 43 5. 无向图连通分支(dfs邻接阵形式) 44 6. 有向图强连通分支(bfs邻接阵...
1. 无向图关键边(dfs邻接阵形式) 41 2. 无向图关键点(dfs邻接阵形式) 42 3. 无向图块(bfs邻接阵形式) 43 4. 无向图连通分支(bfs邻接阵形式) 43 5. 无向图连通分支(dfs邻接阵形式) 44 6. 有向图强连通分支(bfs...
1. 无向图关键边(dfs邻接阵形式) 41 2. 无向图关键点(dfs邻接阵形式) 42 3. 无向图块(bfs邻接阵形式) 43 4. 无向图连通分支(bfs邻接阵形式) 43 5. 无向图连通分支(dfs邻接阵形式) 44 6. 有向图强连通分支(bfs邻接阵...
1. 无向图关键边(dfs邻接阵形式) 41 2. 无向图关键点(dfs邻接阵形式) 42 3. 无向图块(bfs邻接阵形式) 43 4. 无向图连通分支(bfs邻接阵形式) 43 5. 无向图连通分支(dfs邻接阵形式) 44 6. 有向图强连通分支(bfs邻接阵...
1. 无向图关键边(dfs 邻接阵形式) . 41 2. 无向图关键点(dfs 邻接阵形式) . 42 3. 无向图块(bfs 邻接阵形式) .. 43 4. 无向图连通分支(bfs 邻接阵形式) .... 43 5. 无向图连通分支(dfs 邻接阵形式) .... 44 6. 有向...