Tag:网络流
Article From:https://www.cnblogs.com/Khada-Jhin/p/9123408.html

Title Description

Given a directed graph, each side has a capacity C and an expansion cost W. The expansion cost is the cost of expanding the capacity by 1.
Seek:
1、In the case of no dilatancy, the maximum flow of 1 to N;
2、The maximum flow of 1 to N increases the minimum expansion cost required by K.

input

The first line contains three integers N, M, K, which represent the number of points, the number of edges, and the amount of traffic needed to increase. It
The next M row contains four integers u, V, C and W for each row, representing a U from V to C with capacity expansion of W.
N<=1000,M<=5000,K<=10

output

The output file contains two integers, representing the answer to question 1 and question 2 respectively.

 

First, there is nothing to say. The second question is obviously to find the minimum cost maximum flow, and to build the corresponding edge on the second edge direct residual network, without reconstructing the map. As long as the edge right of the first building is given to INF, it can ensure that the side is added second times. The side cause of the second additionIn order to determine the capacity of each side, it is set up to INF, but the total flow is restricted, so a new source point is connected to the original source, with a capacity of K, which ensures the full flow of the graph.

The code is attached at the end.

  1 #include<cmath>
  2 #include<queue>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<iostream>
  6 #include<algorithm>
  7 using namespace std;
  8 queue<int>Q;
  9 int A[5010];
 10 int B[5010];
 11 int C[5010];
 12 int D[5010];
 13 int f[5010];
 14 int vis[5010];
 15 int c[100001];
 16 int d[100001];
 17 int q[100001];
 18 int to[100001];
 19 int val[100001];
 20 int next[100001];
 21 int from[100001];
 22 int head[100001];
 23 int S,T;
 24 int sum;
 25 int ans=0;
 26 int tot=1;
 27 int n,m,k;
 28 int max_flow=0;
 29 int INF=2147483647;
 30 void add(int x,int y,int z,int w)
 31 {
 32     tot++;
 33     next[tot]=head[x];
 34     head[x]=tot;
 35     to[tot]=y;
 36     c[tot]=z;
 37     val[tot]=w;
 38     from[tot]=x;
 39     tot++;
 40     next[tot]=head[y];
 41     head[y]=tot;
 42     to[tot]=x;
 43     c[tot]=0;
 44     val[tot]=-w;
 45     from[tot]=y;
 46 }
 47 int dfs(int x,int maxflow)
 48 {
 49     if(x==T)
 50     {
 51         return maxflow;
 52     }
 53     int used=0;
 54     int nowflow;
 55     for(int i=head[x];i;i=next[i])
 56     {
 57         if(c[i]!=0&&d[to[i]]==d[x]+1)
 58         {
 59             nowflow=dfs(to[i],min(maxflow-used,c[i]));
 60             c[i]-=nowflow;
 61             c[i^1]+=nowflow;
 62             used+=nowflow;
 63             if(nowflow==maxflow)
 64             {
 65                 return maxflow;
 66             }
 67         }
 68     }
 69     if(used==0)
 70     {
 71         d[x]=-1;
 72     }
 73     return used;
 74 }
 75 bool bfs(int S,int T)
 76 {
 77     memset(d,-1,sizeof(d));
 78     memset(q,0,sizeof(q));
 79     d[S]=0;
 80     int l=0;
 81     int r=0;
 82     q[r++]=S;
 83     while(l<r)
 84     {
 85         int now=q[l];
 86         for(int i=head[now];i;i=next[i])
 87         {
 88             if(d[to[i]]==-1&&c[i]!=0)
 89             {
 90                 d[to[i]]=d[now]+1;
 91                 q[r++]=to[i];
 92             }
 93         }
 94         l++;
 95     }
 96     if(d[T]!=-1)
 97     {
 98         return true;
 99     }
100     return false;
101 }
102 void dinic()
103 {
104     while(bfs(S,T)==true)
105     {
106         ans+=dfs(S,INF);
107     }
108 }
109 bool SPFA()
110 {
111     for(int i=0;i<=T;i++)
112     {
113         d[i]=INF;
114     }
115     d[S]=0;
116     Q.push(S);
117     vis[S]=1;
118     while(!Q.empty())
119     {
120         int now=Q.front();
121         Q.pop();
122         vis[now]=0;
123         for(int i=head[now];i;i=next[i])
124         {
125             if(!c[i])
126             {
127                 continue;
128             }
129             if(d[to[i]]>d[now]+val[i])
130             {
131                 d[to[i]]=d[now]+val[i];
132                 f[to[i]]=i;
133                 if(!vis[to[i]])
134                 {
135                     Q.push(to[i]);
136                     vis[to[i]]=1;
137                 }
138             }
139         }
140     }
141     return d[T]!=INF;
142 }
143 void result()
144 {
145     int now=T;
146     int flow=INF;
147     while(now!=S)
148     {
149         flow=min(flow,c[f[now]]);
150         now=from[f[now]];
151     }
152     max_flow+=flow;
153     sum+=d[T]*flow;
154     now=T;
155     while(now!=S)
156     {
157         c[f[now]]-=flow;
158         c[f[now]^1]+=flow;
159         now=from[f[now]];
160     }
161 }
162 void find_min()
163 {
164     while(SPFA())
165     {
166         result();
167     }
168 }
169 int main()
170 {
171     scanf("%d%d%d",&n,&m,&k);
172     S=1;
173     T=n;
174     for(int i=1;i<=m;i++)
175     {
176         scanf("%d%d%d%d",&A[i],&B[i],&C[i],&D[i]);
177         add(A[i],B[i],C[i],0);
178     }
179     dinic();
180     printf("%d ",ans);
181     for(int i=1;i<=m;i++)
182     {
183         add(A[i],B[i],INF,D[i]);
184     }
185     S=0;
186     add(S,1,k,0);
187     find_min();
188     printf("%d",sum);
189 }

 

Leave a Reply

Your email address will not be published. Required fields are marked *