判断边是否在某个最小割集中 以及 判断边是否为最小割的必需边。
在残余网络中求出强连通分量,对于不在同一强连通分量且满流的边,必然在某一最小割中。
题目链接
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define min(a,b) ( (a)< (b)? (a): (b) )
int const N= 4010, M= 60010;
struct Edge{
int adj, flow, idx;
Edge* next;
}tb[M<<1];
int n, m, S, T, cnt;
Edge* mat[N];
inline void add( int u, int v, int idx, int f ){
++cnt;
tb[cnt].adj= v; tb[cnt].flow= f; tb[cnt].idx= idx;
tb[cnt].next= mat[u]; mat[u]= tb+ cnt;
++cnt;
tb[cnt].adj= u; tb[cnt].flow= 0; tb[cnt].idx= 0;
tb[cnt].next= mat[v]; mat[v]= tb+ cnt;
}
inline Edge* reserve( Edge* p ){
return tb+ ( (p- tb)^ 1 ); }
int que[N], head, tail, ht[N];
int bfs(){
for( int i= 0; i<= n; ++i ) ht[i]= -1;
que[0]= S; head= tail= 0; ht[S]= 0;
while( head<= tail ){
int u= que[head++];
for( Edge* p= mat[u]; p; p= p->next )
if( ht[p->adj]== -1 && p->flow ){
ht[p->adj]= ht[u]+ 1;
que[++tail]= p->adj;
}
}
return ht[T]!= -1;
}
int dfs( int u, int flow ){
if( u== T ) return flow;
int tf= 0, f;
for( Edge* p= mat[u]; p; p= p->next )
if( ht[p->adj]== ht[u]+ 1 && p->flow && flow> tf &&
( f= dfs( p->adj, min( p->flow, flow- tf ) ) ) ){
reserve( p )->flow+= f;
p->flow-= f;
tf+= f;
}
if( tf== 0 ) ht[u]= -1;
return tf;
}
int dep[M], low[M], ind[N], stack[N], top, num, id;
void SCC( int u ){
dep[u]= low[u]= ++num; stack[++top]= u;
for( Edge* p= mat[u]; p; p= p->next )
if( p->flow ){
int v= p->adj;
if( dep[v]== 0 ){
SCC( v );
if( low[v]< low[u] ) low[u]= low[v];
}
else if( low[v]!= n && dep[v]< low[u] )
low[u]= low[v];
}
if( dep[u]== low[u] ){
id++;
do{
ind[ stack[top] ]= id;
low[ stack[top] ]= n;
}while( stack[top--]!= u );
}
}
void solve(){
for( int i= 0; i<= n; ++i ){
dep[i]= 0; low[i]= 0; ind[i]= 0; }
num= 0; id= 0; top= -1;
for( int i= 1; i<= n; ++i )
if( dep[i]== 0 ) SCC( i );
for( int i= 0; i<= m; ++i ){
dep[i]= 0; low[i]= 0; }
for( int u= 1; u<= n; ++u )
for( Edge* p= mat[u]; p; p= p->next ){
int v= p->adj;
if( ind[u]!= ind[v] && p->flow== 0 ) dep[p->idx]= 1;
if( ind[u]!= ind[v] && p->flow== 0 &&
ind[u]== ind[S] && ind[v]== ind[T] ) low[p->idx]= 1;
}
for( int i= 1; i<= m; ++i )
printf("%d %d\n", dep[i], low[i] );
}
int main(){
while( scanf("%d%d%d%d", &n, &m, &S, &T )!= EOF ){
cnt= -1;
for( int i= 0; i<= n; ++i ) mat[i]= 0;
int u, v, d;
for( int i= 1; i<= m; ++i ){
scanf("%d%d%d", &u, &v, &d );
add( u, v, i, d );
}
int ans= 0;
while( bfs() ) ans+= dfs( S, 0x7fffffff );
solve();
}
return 0;
}
分享到:
相关推荐
AHOI2009的试题和测试数据,如果有人需要可以看看。
pyh提供,只是顺手转载。。。。 安徽2009NOI省选数据..
ahoi2012年测试数据,安徽省中学组竞赛测试数据
安徽省选AHOI2001-2012试题及数据
ahoi2012试题 安徽省2012年信息学竞赛试题
洛谷P4248 [AHOI2013]差异 的 AC 代码
好论文 关于安徽的比赛情况的介绍的 希望下载啊
最小割性质【AHOI2009】 消圈定理 数据结构 树状斑点 线段树 划分树 平衡树(fhqtreap / splay) LCT 并查集 树 可并堆 可持久化数据结构 数学 数论 gcd / exgcd 费马(线性推逆元)/(EX)欧拉定理 米勒·拉宾...
LOJLOJLOJ 传送门 题解:首先考虑一棵树怎么做,就是树形 dpdpdp,然后我们可以枚举每一条边怎么选,显然有 3 种情况 进一步发现只需要枚举两种,即强制 uuu 选 vvv 不选,和强制 uuu 不选 vvv 随意 ...
作为一个计算机科学家,JYY有一套黑白色的拼图,他希望通过合理的拼接,使得拼出的最终图案中,能包含面积最大的全白色子矩形。之后JYY发现,可以通过改变这S块拼图
【故事背景】宅男JYY非常喜欢玩RPG游戏,比如仙剑,轩辕剑等等。不过JYY喜欢的并不是战斗场景,而是类似电视剧一般的充满恩怨情仇的剧情。这些游戏往往都有很多的
本资源是安徽省信息学奥林匹克OI2012省选资料,内容详实,适合准备参加省选项的高中生。
AOI安徽省青少年信息学奥林匹克竞赛小学组试题 汇总 包含了2014;2013,2011,2010年的试题。
FRAFOS GmbH | Windscheidstr. 18 Ahoi 10627 Berlin Germany | info@frafos.com | ww
coremedia-tools (c) Alexander Lenzen,Ahoi-IT。 mailto-name: al, mailto-domain: ahoi-it.de 有关许可信息,请参阅LICENSE.md 。目的这是一个 CoreMedia 命令行工具包。内容僵尸杀手Zombie-Killer 是一个工具,...
2023安徽“科大国创杯”小学组 试题
目录[TJOI2017]可乐[ZJOI2006]物流运输[HNOI/AHOI2018]道路[ZJOI2007]时态同步[TJOI2017]城市 [TJOI2017]可乐 tag上是分层图+矩阵优化,但是被我用暴力+滚动数组水过去了(赞美O2!)对每个点有三种状态,0:上一秒...