首页 > 代码库 > HDU 2485
HDU 2485
http://acm.hdu.edu.cn/showproblem.php?pid=2485
n个车站,m条边,两边之间费用为1,问最少摧毁多少车站,使得1-n无法在k时间内到达
将2-(n-1)每个点拆成两个,并建立容量为1,费用为0的一条边,源点为1,汇点为2*n-2,这时求最小费用最大流,其中保证dis[t]<=k,求得的最大流即为摧毁的车站数量(因为1流量代表能从其中一个车站到达n点)
#include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std ; const int INF=0xfffffff ; struct node{ int s,t,cap,cost,nxt ; }e[200005] ; int sumflow ; int n,m,k,cnt,head[1005],vis[1005],dis[1005],pre[1005] ; void add(int s,int t,int cap,int cost) { e[cnt].s=s ;e[cnt].t=t ;e[cnt].cap=cap ;e[cnt].cost=cost ;e[cnt].nxt=head[s] ;head[s]=cnt++ ; e[cnt].s=t ;e[cnt].t=s ;e[cnt].cap=0 ;e[cnt].cost=-cost ;e[cnt].nxt=head[t] ;head[t]=cnt++ ; } int spfa(int s,int t,int N) { for(int i=0 ;i<=N ;i++) dis[i]=INF ; dis[s]=0 ; memset(vis,0,sizeof(vis)) ; memset(pre,-1,sizeof(pre)) ; vis[s]=1 ; queue <int> q ; q.push(s) ; while(!q.empty()) { int u=q.front() ; q.pop() ; vis[u]=0 ; for(int i=head[u] ;i!=-1 ;i=e[i].nxt) { int tt=e[i].t ; if(e[i].cap && dis[tt]>dis[u]+e[i].cost) { dis[tt]=dis[u]+e[i].cost ; pre[tt]=i ; if(!vis[tt]) { vis[tt]=1 ; q.push(tt) ; } } } } if(dis[t]==INF || dis[t]>k)return 0 ; return 1 ; } int MCMF(int s,int t,int N) { int flow,minflow,mincost ; mincost=flow=0 ; while(spfa(s,t,N)) { minflow=INF ; for(int i=pre[t] ;i!=-1 ;i=pre[e[i].s]) minflow=min(minflow,e[i].cap) ; flow+=minflow ; for(int i=pre[t] ;i!=-1 ;i=pre[e[i].s]) { e[i].cap-=minflow ; e[i^1].cap+=minflow ; } mincost+=dis[t]*minflow ; } sumflow=flow ;//最大流 return mincost ; } int main() { while(scanf("%d%d%d",&n,&m,&k)) { if(!n && !m && !k)break ; cnt=0 ; memset(head,-1,sizeof(head)) ; int s=1 ; int t=2*n-2 ; for(int i=1 ;i<n-1 ;i++) add(2*i,2*i+1,1,0) ; while(m--) { int a,b ; scanf("%d%d",&a,&b) ; a-- ;b-- ; add(a*2+1,b*2,1,1) ; } MCMF(s,t,t) ; printf("%d\n",sumflow) ; } return 0 ; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。