bzoj1797: [Ahoi2009]Mincut 最小割(网络流,缩点)
2024-09-05 05:13:27
传送门
首先肯定要跑一个最小割也就是最大流
然后我们把残量网络tarjan,用所有没有满流的边来缩点
一条边如果没有满流,那它就不可能被割了
一条边如果所属的两个强联通分量不同,它就可以被割
一条边如果所属的两个点一个与源点同块,一个与汇点同块,那么它就可以一定在最小割集合中
为啥我也不会证,直接搬一下隔壁的吧
1.将每个SCC缩成一个点,得到的新图就只含有满流边了。那么新图的任一s-t割都对应原图的某个最小割,从中任取一个把id[u]和id[v]割开的割即可证明。
2.假设将(u,v)的边权增大,那么残余网络中会出现s->u->v->t的通路,从而能继续增广,于是最大流流量(也就是最小割容量)会增大。这即说明(u,v)是最小割集中必须出现的边。
//minamoto
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,:;}
inline int read(){
#define num ch-'0'
char ch;bool flag=;int res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
const int N=,M=;
int head[N],Next[M],ver[M],edge[M],tot=;
inline void add(int u,int v,int e){
ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e;
ver[++tot]=u,Next[tot]=head[v],head[v]=tot,edge[tot]=;
}
int dep[N],cur[N],s,t,n,m;
queue<int> q;
bool bfs(){
memset(dep,-,sizeof(dep));
while(!q.empty()) q.pop();
for(int i=;i<=n;++i) cur[i]=head[i];
q.push(s),dep[s]=;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i;i=Next[i]){
int v=ver[i];
if(dep[v]<&&edge[i]){
dep[v]=dep[u]+,q.push(v);
if(v==t) return true;
}
}
}
return false;
}
int dfs(int u,int limit){
if(u==t||!limit) return limit;
int flow=,f;
for(int i=cur[u];i;i=Next[i]){
int v=ver[i];cur[u]=i;
if(dep[v]==dep[u]+&&(f=dfs(v,min(limit,edge[i])))){
flow+=f,limit-=f;
edge[i]-=f,edge[i^]+=f;
if(!limit) break;
}
}
if(!flow) dep[u]=-;
return flow;
}
int dfn[N],low[N],st[N],c[N],top,cnt,num;
void tarjan(int u){
dfn[u]=low[u]=++num,st[++top]=u;
for(int i=head[u];i;i=Next[i])
if(edge[i]){
int v=ver[i];
if(!dfn[v]) tarjan(v),cmin(low[u],low[v]);
else if(!c[v]) cmin(low[u],dfn[v]);
}
if(dfn[u]==low[u])
for(++cnt;st[top+]!=u;--top) c[st[top]]=cnt;
}
int main(){
//freopen("testdata.in","r",stdin);
n=read(),m=read(),s=read(),t=read();
for(int i=;i<=m;++i){
int u=read(),v=read(),e=read();add(u,v,e);
}
while(bfs()) dfs(s,inf);
for(int i=;i<=n;++i)
if(!dfn[i]) tarjan(i);
for(int i=;i<=tot;i+=){
printf("%d %d\n",!edge[i]&&c[ver[i]]!=c[ver[i^]],c[ver[i^]]==c[s]&&c[ver[i]]==c[t]);
}
return ;
}
最新文章
- PostgreSQL杀掉死锁的链接
- 【http代理报文】通过发包实现代理请求网页内容
- Linux下c开发 之 线程通信(转)
- android 6.0添加权限
- codeforces 336 Div.2 B. Hamming Distance Sum
- Inside of Jemalloc
- [Bhatia.Matrix Analysis.Solutions to Exercises and Problems]ExI.4.1
- Android学习总结——Popup menu:弹出式菜单
- 学习笔记TF041:分布式并行
- 状态压缩- Brackets
- 通俗理解N-gram语言模型。(转)
- tomcat报java.lang.VerifyError错误
- ajax中的contendType和dataType知识点梳理
- 【APT】SqlServer游标使用
- 使用系统的CoreLocation定位
- 分别给Python类和实例增加属性和方法
- Fluent Python: Classmethod vs Staticmethod
- P2085 最小函数值(minval)
- devstack环境搭建
- MySQL查询优化方法总结
热门文章
- docker国内镜像加速
- 1.3.3 并发容器类MAP/LIST/SET/QUEUE
- Django-djangorestframework-渲染模块
- Redis学习存档(2)——通过Java使用Redis:Jedis
- 【思维】Kenken Race
- 指针生成网络(Pointer-Generator-Network)原理与实战
- MySQL SQL Training
- 怎样测试nginx.conf配置文件的正确性
- Web API 接口版本控制 SDammann.WebApi.Versioning
- 微信小程使用getCurrentPages函数操作父级数据