`
darren_nizna
  • 浏览: 72761 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

[AHOI2009][Mincut 最小割]

F# 
阅读更多

判断边是否在某个最小割集中 以及 判断边是否为最小割的必需边。

在残余网络中求出强连通分量,对于不在同一强连通分量且满流的边,必然在某一最小割中。

题目链接

 

#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试题与测试数据

    《AHOI2009试题与测试数据详解》 AHOI,全称为"全国青少年信息学奥林匹克竞赛"(All-China High School Informatics Olympiad),是中国一项极具影响力的信息学竞赛,旨在选拔并培养优秀的信息技术人才。AHOI2009是...

    AHOI2009数据

    2. `mincut`:这个名字暗示了最小割问题,这是一个经典的图论问题,通常用在网络流或最短路径算法中,比如Karger's Algorithm。 3. `checker`:可能是一个自动检查程序输出正确性的工具,用于验证参赛者代码的解决...

    安徽省选AHOI试题及数据

    在这些资源中,安徽省选AHOI试题及数据尤为引人注目,它记录了从2001年到2012年间的安徽省信息学奥林匹克竞赛(AHOI)的发展脉络。 AHOI作为一项面对省内青少年的信息学竞赛,从试题设计到参赛数据的整理,均体现了...

    ahoi2012测试数据

    **ahoi2012测试数据详解** "ahoi2012测试数据"是针对安徽省中学组竞赛的一份重要资料,它包含了该年度比赛所使用的试题和样例输入输出,旨在帮助参赛者熟悉竞赛环境,提升算法设计与编程能力。这类测试数据通常包括...

    ahoi2012试题

    在“ahoi2012试题”这个压缩包中,很可能包含了一系列的编程题目,这些题目可能涵盖了从基础的逻辑思维到高级的算法设计,包括但不限于以下知识点: 1. **基础编程概念**:参赛者需要熟悉至少一种编程语言,如C++、...

    洛谷P4248 AHOI2013差异 的 AC 代码

    洛谷P4248 [AHOI2013]差异 的 AC 代码

    论文AHOI’1993-2004年安徽省青少年信息学奥林匹克竞赛\AHOI团体获奖情况.doc

    安徽省青少年信息学奥林匹克竞赛(AHOI)是针对青少年的一项重要的信息技术类竞赛,自1993年开始举办,旨在激发学生对计算机科学的兴趣,提升他们的编程能力与算法设计技巧。通过对1993年至2004年间AHOI团体获奖情况...

    # AHOI2008 紧急集合 / 聚会

    # [AHOI2008] 紧急集合 / 聚会 ## 题目描述 欢乐岛上有个非常好玩的游戏,叫做“紧急集合”。在岛上分散有 $n$ 个等待点,有 $n-1$ 条道路连接着它们,每一条道路都连接某两个等待点,且通过这些道路可以走遍所有...

    OI来源:OI代码仓库,复习笔记,代码模板,本地法官

    最小割性质【AHOI2009】 消圈定理 数据结构 树状斑点 线段树 划分树 平衡树(fhqtreap / splay) LCT 并查集 树 可并堆 可持久化数据结构 数学 数论 gcd / exgcd 费马(线性推逆元)/(EX)欧拉定理 米勒·拉宾...

    「AHOI / HNOI2018」毒瘤 (DDP)(链分治)

    LOJLOJLOJ 传送门 题解:首先考虑一棵树怎么做,就是树形 dpdpdp,然后我们可以枚举每一条边怎么选,显然有 3 种情况 进一步发现只需要枚举两种,即强制 uuu 选 vvv 不选,和强制 uuu 不选 vvv 随意 ...

    wangjunrui666#bzoj-problem##3873. [Ahoi2014&amp;Jsoi2014]拼图1

    作为一个计算机科学家,JYY有一套黑白色的拼图,他希望通过合理的拼接,使得拼出的最终图案中,能包含面积最大的全白色子矩形。之后JYY发现,可以通过改变这S块拼图

    wangjunrui666#bzoj-problem##3876. [Ahoi2014&amp;Jsoi2014]支线剧情1

    【故事背景】宅男JYY非常喜欢玩RPG游戏,比如仙剑,轩辕剑等等。不过JYY喜欢的并不是战斗场景,而是类似电视剧一般的充满恩怨情仇的剧情。这些游戏往往都有很多的

    AOI安徽省青少年信息学奥林匹克竞赛小学组试题

    AOI安徽省青少年信息学奥林匹克竞赛是针对小学组的信息学竞赛,主要是为了提高安徽省青少年对信息学的兴趣和逻辑思维能力,锻炼他们的计算思维和编程技能。该竞赛涉及的题目类型主要分为传统型,即给定具体的算法...

    树上倍增_黄哲威.pdf

    * AHOI2008:树上倍增算法可以用于解决AHOI2008问题,即求解树上三点的最近公共祖先。 * NOIP2013:树上倍增算法可以用于解决NOIP2013问题,即求解树上两点的最短路径。 树上倍增算法是一种非常有用的算法,用于...

    2023安徽“科大国创杯”小学组 试题

    问题描述:给定一个质数 p,定义一个数 x(1 ≤ x ) 模 p 的阶为:最小的正整数 t 使得 xt 模 p 等于 1(即 xt 除以 p 的余数为 1)。请帮助小多算若干组阶。 输入格式:输入文件名为 order.in。第一行是一个正整数 ...

    coremedia-tools

    coremedia-tools (c) Alexander Lenzen,Ahoi-IT。 mailto-name: al, mailto-domain: ahoi-it.de 有关许可信息,请参阅LICENSE.md 。目的这是一个 CoreMedia 命令行工具包。内容僵尸杀手Zombie-Killer 是一个工具,...

    蒟蒻の图论刷题(更新中)Ⅰ 树/图dp

    目录[TJOI2017]可乐[ZJOI2006]物流运输[HNOI/AHOI2018]道路[ZJOI2007]时态同步[TJOI2017]城市 [TJOI2017]可乐 tag上是分层图+矩阵优化,但是被我用暴力+滚动数组水过去了(赞美O2!)对每个点有三种状态,0:上一秒...

    【OI】AOI安徽省选2007试题

    在"AHOI2007"这个压缩包中,可能包含了当年比赛的题目描述、输入输出样例、解题报告等资源,对于学习信息学竞赛的学生或者对此感兴趣的人,这是一个宝贵的资料库。通过深入研究这些题目,不仅能提升编程能力,还能...

    mysql主从双机同步

    mysql&gt; grant all privileges on *.* to ahoi@'%' identified by '123456'; ``` 这一步骤是安全和同步的基础,确保了从机可以合法地从主机获取数据更新。 #### 主机配置 在主机的MySQL配置文件`/etc/my.cnf`中添加...

Global site tag (gtag.js) - Google Analytics