首页 > 代码库 > hdu 2485 Destroying the bus stations 最小费用最大流

hdu 2485 Destroying the bus stations 最小费用最大流

2024-07-24 15:08:22   213人阅读

题意：

　　最少需要几个点才能使得有向图中1->n的距离大于k。

 

分析：

　　删除某一点的以后，与它相连的所有边都不存在了，相当于点的容量为1。但是在网络流中我们只能直接限制边的容量。所以需要拆点来完成对的点容量的限制。对于边i -> j，先建边i ->i‘,再建i‘->j。i ->i‘只能建一次，容量为1，费用为0。i‘->j的容量是INF。此题中因为已经有源点，所以源点（1）不能限制容量。

 

  1 #include<iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 using namespace std;  6 const int N =110, M=10010,INF=0x3f3f3f3f;  7 struct node  8 {  9     int to, next, c ,f;//c是容量，f是费用 10 }edge[M]; 11 int head[N],dis[N],load[N],p[N]; 12 bool vis[N]; 13 int tot,flow,ans,D; 14 bool spfa(int S, int E,int n) 15 { 16     int que[N*10],qout,qin; 17     memset(vis,0,sizeof(vis)); 18     memset(load,-1,sizeof(load)); 19     memset(p,-1,sizeof(p)); 20     for(int i=0;i<=n;i++) 21         dis[i]=INF; 22     qin=qout=0; 23     que[qin++]=S; 24     dis[S]=0; 25     vis[S]=1; 26     while(qin!=qout) 27     { 28         int u=que[qout++]; 29         vis[u]=0; 30         for(int i=head[u];i!=-1;i=edge[i].next) 31         { 32             if(edge[i].c) 33             { 34                 int v=edge[i].to; 35                 if(dis[v]-dis[u]>edge[i].f) 36                 { 37                     dis[v]=dis[u]+edge[i].f; 38                     p[v]=u; 39                     load[v]=i; 40                     if(!vis[v]) 41                     { 42                         vis[v]=1; 43                         que[qin++]=v; 44                     } 45                 } 46             } 47         } 48     } 49     if(dis[E]>D) return 0; 50     return 1; 51 } 52 void MCF(int S, int E,int n) 53 { 54     int u,mn; 55     flow=ans=0; 56     while(spfa(S,E,n)) 57     { 58         u=E; mn=INF; 59         while(p[u]!=-1) 60         { 61             mn=min(edge[load[u]].c, mn); 62             u=p[u]; 63         } 64         u=E; 65         while(p[u]!=-1) 66         { 67             edge[load[u]].c-=mn; 68             edge[load[u]^1].c+=mn; 69             u=p[u]; 70         } 71         ans+=dis[E]*mn; 72         flow+=mn; 73     } 74 } 75 void addedge(int a,int b,int c,int d) 76 { 77     edge[tot].to=b;edge[tot].c=c;edge[tot].f=d; 78     edge[tot].next=head[a];head[a]=tot++; 79     edge[tot].to=a;edge[tot].c=0;edge[tot].f=-d; 80     edge[tot].next=head[b];head[b]=tot++; 81 } 82 void init() 83 { 84     tot=0; 85     memset(head,-1,sizeof(head)); 86 } 87 int main() 88 { 89     //freopen("test.txt","r",stdin); 90     int n,m,i,j,k; 91     while(scanf("%d%d%d",&n,&m,&D)!=EOF&&n) 92     { 93         init(); 94         while(m--) 95         { 96             scanf("%d%d",&i,&j); 97             if(i!=1) addedge(i+n,j,INF,1); 98             else addedge(i,j,INF,1); 99         }100         for(i=2;i<n;i++) addedge(i,i+n,1,0);101         MCF(1,n,2*n);102         printf("%d\n",flow);103     }104     return 0;105 }
View Code

 

hdu 2485 Destroying the bus stations 最小费用最大流


联系
我们