【最大流/费用流】BZOJ1834-[ZJOI2010]network 网络扩容

【题目大意】

给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求： 1、在不扩容的情况下，1到N的最大流； 2、将1到N的最大流增加K所需的最小扩容费用。

【思路】

问题用Dinic搞一搞。问题二可以看出是费用流。

(1)残余网络中边还有一些容量，而如果利用这些容量，是不需要花费新的费用的。则将这些边的费用设置为0。

(2)对于原有的边，添加一条起点、终点相同的点，容量设置为INF，费用设置为一开始输入的扩容费用。再添加一个超级源点，和1之间添加一条边，容量为K，费用为0。

所谓的费用流，就是将EK中每一次搜索改为关于单位费用的SPFA即可，其余板块类似。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<vector>
  6 #include<queue> 
  7 using namespace std;
  8 const int MAXN=1000+50;
  9 const int MAXM=5000+50;
 10 const int INF=0x7fffffff;
 11 int n,m,k;//点数边数和需要扩充的容量 
 12 struct node
 13 {
 14     int to,cap,pos,w;
 15 };
 16 vector<node> E[MAXN];
 17 int vis[MAXN];
 18 int dis[MAXN];
 19 int U[MAXM],V[MAXM],C[MAXM],W[MAXM];
 20 int pre[MAXN],preedge[MAXN];//记录每次SPFA中每一个节点的前驱,以及当前节点在前驱的vector中是第几条边 
 21 
 22 void addedge(int u,int v,int c,int w)
 23 {
 24     E[u].push_back((node){v,c,E[v].size(),w});
 25     E[v].push_back((node){u,0,E[u].size()-1,-w});/*失误把这里敲成了E[u]，看了好久才看出来T T*/ 
 26 }
 27 
 28 void init()
 29 {
 30     scanf("%d%d%d",&n,&m,&k);
 31     for (int i=0;i<m;i++)
 32     {
 33         scanf("%d%d%d%d",&U[i],&V[i],&C[i],&W[i]);
 34         addedge(U[i],V[i],C[i],0);
 35     }
 36 }
 37 
 38 int bfs()
 39 {
 40     queue<int> que;
 41     memset(dis,-1,sizeof(dis));
 42     dis[1]=0;
 43     que.push(1);
 44     while (!que.empty())
 45     {
 46         int head=que.front();que.pop();
 47         for (int i=0;i<E[head].size();i++)
 48         {
 49             node tmp=E[head][i];
 50             if (dis[tmp.to]==-1 && tmp.cap>0)
 51             {
 52                 dis[tmp.to]=dis[head]+1;
 53                 que.push(tmp.to);
 54             }
 55         } 
 56     }
 57     if (dis[n]==-1) return 0;
 58         else return 1;
 59 }
 60 
 61 int dfs(int s,int e,int f)
 62 {
 63     vis[s]=1;
 64     if (s==e) return f;
 65     for (int i=0;i<E[s].size();i++)
 66     {
 67         node& tmp=E[s][i];
 68         if (!vis[tmp.to] && tmp.cap>0 && dis[tmp.to]==dis[s]+1)
 69         {
 70             int delta=dfs(tmp.to,e,min(f,tmp.cap));
 71             if (delta>0)
 72             {
 73                 tmp.cap-=delta;
 74                 E[tmp.to][tmp.pos].cap+=delta;
 75                 return delta;
 76             }
 77         }
 78     }
 79     return 0;
 80 }
 81 
 82 void dinic()
 83 {
 84     int flow=0;
 85     while (bfs())
 86     {
 87         memset(vis,0,sizeof(vis));
 88         int f=dfs(1,n,INF);
 89         if (f==0) break;
 90             else flow+=f;
 91     }
 92     cout<<flow<<' '; 
 93 }
 94 
 95 void rebuild()
 96 {
 97     for (int i=0;i<m;i++) addedge(U[i],V[i],INF,W[i]);
 98     addedge(0,1,k,0);
 99 }
100 
101 int spfa(int u,int v)
102 {
103     memset(vis,0,sizeof(vis));
104     for (int i=0;i<=n;i++) dis[i]=INF;
105     memset(pre,-1,sizeof(pre));
106     queue<int> que;
107     dis[0]=0;
108     vis[0]=1;
109     que.push(0);
110     while (!que.empty())
111     {
112         int head=que.front();
113         que.pop();
114         vis[head]=0;
115         for (int i=0;i<E[head].size();i++)
116         {
117             node& tmp=E[head][i];
118             if (tmp.cap>0 && dis[tmp.to]>dis[head]+tmp.w)
119             {
120                 dis[tmp.to]=dis[head]+tmp.w;
121                 pre[tmp.to]=head;
122                 preedge[tmp.to]=i;
123                 if (!vis[tmp.to])
124                 {
125                     vis[tmp.to]=1;
126                     que.push(tmp.to);
127                 }
128             }
129         }
130     }
131     if (dis[n]==INF) return 0;
132     else return 1;
133 }
134 
135 void mcf()
136 {
137     int ans=0;
138     while (spfa(1,n))
139     {
140         int flow=INF;
141         for (int i=n;pre[i]!=-1;i=pre[i])
142             flow=min(flow,E[pre[i]][preedge[i]].cap);
143         for (int i=n;pre[i]!=-1;i=pre[i])
144         {
145             node& tmp=E[pre[i]][preedge[i]];
146             tmp.cap-=flow;
147             E[tmp.to][tmp.pos].cap+=flow;
148             ans+=flow*tmp.w;
149         }
150     }
151     cout<<ans<<endl; 
152 }
153 
154 int main()
155 {
156     init();
157     dinic();
158     rebuild(); 
159     mcf();
160     return 0;
161 }