【2016/5/25 考题】toll 简洁巧妙的网络流
题意： N 个点，M 条边的有向图，在每条边 (ui,vi) 上建立收费站需要花费 ci，问要使得从 1 号点到 N 号点的任意一条路径都经过且只经过一个收费站，所需要的最小代价。 (N<=100 , M<=2500)
如果题目不要求只经过一个收费站，那么就是裸的最小割，跑一遍 Dinic 即可。
但是现在题目要求只能经过一个，应该怎么办呢？
考虑跑最小割时什么情况下会出现一条路径经过两个收费站。
如图，1 为 源点 S，汇点 T 未画出。选择的 (2,3) 和 (4,5)，这样便会不合法。
我们来考虑如何避免这样的情况，即对于一条边 (u,v)，避免通过同时割掉 S 到 u 路径上和 v 到 T 路径上的各一条边。
注意到，如果连了一条容量无穷的边(a,b)，说明 S 到 a 或者 b 到 T 至少有一边会被割掉。于是我们有了一个想法，对于原图的边 (u,v)，连一条 (v,u)，容量为正无穷，即 S 到 v 或者 u 到 T至少有一边会被割掉。由于是最小割，S 到 p 和 p 到 T 不会同时被割掉，于是若我们割了 S 到 v 则不会割 v 到 Ｔ，若割了 u 到 T 则不会割 S 到 u。也就是说，现在就一定满足限制了。
所以概括来说，建原图的边(u,v)，容量为 ci；以及一条反向的边 (v,u)，容量为正无穷。跑最大流即可。构图实际上很简单，但是需要对网络流有较为深刻的理解，而这道题也不失为一道好题。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long INF=(1ll<<60)-1 , cap[10005] ;
int first[10005] , nexts[10005] , to[10005] , egnum=1 , cur[10005] , que[10005] , head , tail , d[10005] ;
int n,m ;
void add_edge(int a,int b,long long c){
nexts[++egnum]=first[a] , first[a]=egnum , to[egnum]=b , cap[egnum]=c ;
nexts[++egnum]=first[b] , first[b]=egnum , to[egnum]=a , cap[egnum]=0 ;
}
bool BFS(){
memset(d,0,sizeof(int)*(n+15)) ;
d[1]=1 , head=tail=0 ;
que[tail++]=1 ;
while(head<tail){
int a=que[head++] ;
for(int i=first[a];i;i=nexts[i]){
if(cap[i] && !d[to[i]])d[to[i]]=d[a]+1 , que[tail++]=to[i] ;
}
}
return d[n] ;
}
long long DFS(int a,long long flow){
if(!flow || a==n)return flow ;
int &i=cur[a] ;
if(i==-1)i=first[a] ;
long long ret=0 ;
for(;i;i=nexts[i]){
int b=to[i] ;
if(!cap[i] || d[b]!=d[a]+1)continue ;
long long t=DFS(b,min(flow,cap[i])) ;
cap[i]-=t , cap[i^1]+=t , flow-=t , ret+=t ;
if(!flow)break ;
}
return ret;
}
long long Dinic(){
long long ret=0 ;
while(BFS()){
memset(cur,-1,sizeof(int)*(n+15)) ;
ret+=DFS(1,INF) ;
if(ret>=INF){ ret=-1 ; break ; }
}
return ret;
}
int main(){
freopen("toll.in","r",stdin) ;
freopen("toll.out","w",stdout) ;
scanf("%d%d",&n,&m) ;
for(int i=1;i<=m;++i){
int a,b,c;
scanf("%d%d%d",&a,&b,&c) , add_edge(a,b,c) , add_edge(b,a,INF) ;
}
long long ans=Dinic() ;
printf("%lld\n",ans) ;
return 0 ;
}
评论