题解 P2604 【[ZJOI2010]网络扩容】
Npse_D
2018-04-03 17:22:01
我用两种方法做了这个题，恰巧都是题解里出现过的方法……
第一问需要你考虑这个问题：
这是一道网络流题目还是一道费用流题目。
显然这是一道费用流题目，因为它第一问是裸的最大流。所以无论如何都要跑费用流，第二问的图还比第一问多一倍的边。
嗯……
所以本着O（cn）==O（n）的原则，拿w==0的EK跑最大流就可以……
更何况第二问的图比第一问复杂，c可能是小于等于2的……
再写一遍Dinic的都是老实人。
第二问。。。
作为费用流题目，最重要的当然是建图。不过这个题建图思路非常显然，本蒟蒻都能瞬间想到。。。。
两个显然的思路：
①增加源流
②限制汇流
。。。。。。。
大概可以想象一下，如果要给自己家的水流扩流一个准确的值k，最暴力的方法就是把所有的管子都加粗到无限粗，保证水都能流过来，然后两个途径，一是让自来水厂给自己maxf+k的水（把它看成是新的一个水流），这样顶多也就maxf+k的水。但管子除了k管儿，其它管子又是无限粗的，所以带费用的最大流又至少是maxf+k，因此最大流就是准确的maxf+k了。二是装一个maxf（扩流前的最大流）+k大的水龙头，这样就刚好能扩k的水了。
可能有点瑕疵，大体意思差不多。。。
所以经过思考后，交上程序成功WA掉。。。
后来想了想，是因为没有重置每一个流的容量。
因为不重置容量的话，就是已经流过maxf。再流maxf，它相当于流了2maxf+k的流。
所以这里就有两个办法了，一是复制一份新图，一份拿来做最大流，一份拿来做最小费用流。下面的神犇可能是用这种方法做的，所以用了maxf+k。二是干脆把所有的maxf+k都当成k。。。。
虽然不怎么会证明，但可以想一下，扩容前和扩容后的流的状态f(x)是可减的…那么最优的免费流的状态是不会因扩容而影响到的，那么这个maxf在扩容前和扩容后都是免费的，而k则都一定会被收费。那么刚刚跑完的最大流，在新图里免费流量的状态是完全重合的。所以我们直接用原来的图，假装自己已经跑过maxf了，然后直接加个k就可以了。
实现：
实现就简单炸了……
①的实现就是让0到1连一个顶多流k的流。
②就是让n到n+1连一个流k的流。。。。
代码：
①
```cpp
#include<bits/stdc++.h>
using namespace std;
const int inf = 123599857;
struct node{
int to;
int cap;
int cost;
int coc;
bool type;
};
vector<node>data[1005];
int pre1[1005],pre2[1005],dx[1005],incf[1005],costed[1005][1005],n,m,k,maxf,ans,s;
bool inq[1005];
inline void add(int u,int v,int w,int f){
data[u].push_back((node){v,w,f,data[v].size(),1});
data[v].push_back((node){u,0,-f,data[v].size()-1,0});
}
inline bool spfa(){
fill(dx+1,dx+n+1,inf);
queue<int>q;
memset(inq,0,sizeof(inq));
q.push(s);
inq[s]=1;
dx[s]=0;
incf[s]=inf;
while(!q.empty()){
int now=q.front();
q.pop();
inq[now]=0;
for(int j=0;j<data[now].size();j++){
node &tmp=data[now][j];
if(tmp.cap>0&&dx[tmp.to]>dx[now]+tmp.cost){
dx[tmp.to]=dx[now]+tmp.cost;
pre1[tmp.to]=now;
pre2[tmp.to]=j;
incf[tmp.to]=min(tmp.cap,incf[now]);
if(!inq[tmp.to]){
q.push(tmp.to);
inq[tmp.to]=1;
}
}
}
}
return dx[n]!=inf;
}
inline void updata(){
int x=n;
while(x!=s){
int y=pre1[x],i=pre2[x];
node &tmp=data[y][i];
tmp.cap-=incf[n];
data[tmp.to][tmp.coc].cap+=incf[n];
x=y;
}
maxf+=incf[n],ans+=dx[n]*incf[n];
}
void solve(){while(spfa())updata();}
int main(){
cin>>n>>m>>k;
s=1;
for(int i=1;i<=m;i++){
int u,v,c,w;
cin>>u>>v>>c>>w;
costed[u][v]=w;
add(u,v,c,0);
}
solve();
cout<<maxf<<" ";
for(int i=1;i<=n;i++){
int coc=data[i].size();
for(int j=0;j<coc;j++){
if(data[i][j].type)add(i,data[i][j].to,100000000,costed[i][data[i][j].to]);
}
}
s=0;
add(0,1,k,0);
solve();
cout<<ans;
}
```
②
```cpp
#include<bits/stdc++.h>
using namespace std;
const int inf = 123599857;
struct node{
int to;
int cap;
int cost;
int coc;
bool type;
};
vector<node>data[1005];
int pre1[1005],pre2[1005],dx[1005],incf[1005],costed[1005][1005],n,m,k,t,maxf,ans;
bool inq[1005];
inline void add(int u,int v,int w,int f){
data[u].push_back((node){v,w,f,data[v].size(),1});
data[v].push_back((node){u,0,-f,data[v].size()-1,0});
}
inline bool spfa(){
fill(dx+1,dx+n+1,inf);
queue<int>q;
memset(inq,0,sizeof(inq));
q.push(1);
inq[1]=1;
dx[1]=0;
incf[1]=inf;
while(!q.empty()){
int now=q.front();
q.pop();
inq[now]=0;
for(int j=0;j<data[now].size();j++){
node &tmp=data[now][j];
if(tmp.cap>0&&dx[tmp.to]>dx[now]+tmp.cost){
dx[tmp.to]=dx[now]+tmp.cost;
pre1[tmp.to]=now;
pre2[tmp.to]=j;
incf[tmp.to]=min(tmp.cap,incf[now]);
if(!inq[tmp.to]){
q.push(tmp.to);
inq[tmp.to]=1;
}
}
}
}
return dx[n]!=inf;
}
inline void updata(){
int x=n;
while(x!=1){
int y=pre1[x],i=pre2[x];
node &tmp=data[y][i];
tmp.cap-=incf[n];
data[tmp.to][tmp.coc].cap+=incf[n];
x=y;
}
maxf+=incf[n],ans+=dx[n]*incf[n];
}
void solve(){while(spfa())updata();}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
int u,v,c,w;
cin>>u>>v>>c>>w;
costed[u][v]=w;
add(u,v,c,0);
}
t=0;
solve();
cout<<maxf<<" ";
for(int i=1;i<=n;i++){
int coc=data[i].size();
for(int j=0;j<coc;j++){
if(data[i][j].type)add(i,data[i][j].to,k,costed[i][data[i][j].to]);
}
}
n++;
add(n-1,n,k,0);
solve();
cout<<ans;
}
```