首页 > 代码库 > 【最短路】【spfa】【最小割】【Dinic】bzoj1266 [AHOI2006]上学路线route
【最短路】【spfa】【最小割】【Dinic】bzoj1266 [AHOI2006]上学路线route
原问题等价于断掉一些边，让原来所有的最短路全都无法联通S和T。
先求最短路，然后把在最短路上的边(dis[u[i]]+w[i]==dis[v[i]])加入新图里，跑最小割。显然。
注意是无向图。
#include<cstdio>#include<cstring>#include<queue>#include<algorithm>using namespace std;#define INF 2147483647#define MAXN 511#define MAXM 505001int n,m,S,T,Sta,End,Ws[260000],W,C;queue<int>q;namespace Dinic{ int v[MAXM],cap[MAXM],en,first[MAXN],next[MAXM]; int d[MAXN],cur[MAXN]; void Init_Dinic(){memset(first,-1,sizeof(first)); en=0; S=1; T=n;} void AddEdge(const int &U,const int &V,const int &W) {v[en]=V; cap[en]=W; next[en]=first[U]; first[U]=en++; v[en]=U; next[en]=first[V]; first[V]=en++;} bool bfs() { memset(d,-1,sizeof(d)); q.push(S); d[S]=0; while(!q.empty()) { int U=q.front(); q.pop(); for(int i=first[U];i!=-1;i=next[i]) if(d[v[i]]==-1 && cap[i]) { d[v[i]]=d[U]+1; q.push(v[i]); } } return d[T]!=-1; } int dfs(int U,int a) { if(U==T || !a) return a; int Flow=0,f; for(int &i=cur[U];i!=-1;i=next[i]) if(d[U]+1==d[v[i]] && (f=dfs(v[i],min(a,cap[i])))) { cap[i]-=f; cap[i^1]+=f; Flow+=f; a-=f; if(!a) break; } if(!Flow) d[U]=-1; return Flow; } int max_flow() { int Flow=0,tmp=0; while(bfs()) { memcpy(cur,first,(n+5)*sizeof(int)); while(tmp=dfs(S,INF)) Flow+=tmp; } return Flow; }};namespace SPFA{ int u[260000],next[260000],v[260000],first[501],w[260000],en,dis[501]; bool inq[501]; void AddEdge(const int &U,const int &V,const int &W,const int &C) {u[++en]=U; v[en]=V; w[en]=W; Ws[en]=C; next[en]=first[U]; first[U]=en;} void spfa(const int &s) { memset(dis,0x7f,sizeof(dis)); dis[s]=0; inq[s]=1; q.push(s); while(!q.empty()) { int U=q.front(); for(int i=first[U];i;i=next[i]) if(dis[v[i]]>dis[U]+w[i]) { dis[v[i]]=dis[U]+w[i]; if(!inq[v[i]]) q.push(v[i]),inq[v[i]]=1; } q.pop(); inq[U]=0; } } void Rebuild_Graph() { Dinic::Init_Dinic(); for(int i=1;i<=(m<<1);++i) if(dis[u[i]]+w[i]==dis[v[i]]) Dinic::AddEdge(u[i],v[i],Ws[i]); }};int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;++i) { scanf("%d%d%d%d",&Sta,&End,&W,&C); SPFA::AddEdge(Sta,End,W,C); SPFA::AddEdge(End,Sta,W,C); } SPFA::spfa(1); SPFA::Rebuild_Graph(); printf("%d\n%d\n",SPFA::dis[n],Dinic::max_flow()); return 0;}
【最短路】【spfa】【最小割】【Dinic】bzoj1266 [AHOI2006]上学路线route
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。