[ZJOI2010]网络扩容[网络流24题]

题意：

给定一张有向图，每条边都有一个容量 c 和一个扩容费用 w。这里扩容费用是指将容量扩大 1 所需的费用。求：

在不扩容的情况下，1 到 n 的最大流；
将 1 到 n 的最大流增加 k 所需的最小扩容费用

题解：

第一问好说就是跑最大流，关键是第二问怎么想
两个方法：
其实本质也是一个，我们可以将扩容的费用转化为增加一点流量，花费W的费用，因为我们要让费用尽可能低，所以问题就成了最小费用流的模型
如何建图呢？
我们可以在第一问的基础上继续建图，也可以重新建图（个人倾向第一种）
如果是第一种，我们在跑完最大流后，利用残余网络继续建图，（第一问建图中每条弧的费用都是0的），我们再在第i条弧的两端之间建一条弧，弧的容量为INF，费用是cost[i],这样保证费用是最低的
但是题目要求是增加k，怎么能控制这个量呢？我们只需要在建立一个超级源点或者超级汇点（建立一个即可），连接S（T），容量为K，费用为0，也就是我们限制流入量或者流出量最多为K即可

代码：

调了半天，终于写出来了。。。。
注意cnt要从1开始
因为0和1是一对相反边，2和3是一对。。。

#include<bits/stdc++.h>
#define inf 0x3f3f3f
#define mem(x,a) memset(x,a,sizeof(x))
typedef long long ll;
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
   return s*w;
}
int n,m,k;
int S,T,cnt=1;
const int maxn=1e6+9;
struct node{
    int u,v,w,cost,next;
}edge[maxn];
int head[maxn],dis[maxn],uu[maxn],vv[maxn],ww[maxn];

inline void add_edge(int u,int v,int w,int dis)
{
    edge[++cnt].next=head[u];
    edge[cnt].u=u;
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].cost=dis;
    head[u]=cnt;
}
void add(int u,int v,int w,int dis)
{
    add_edge(u,v,w,dis);
    add_edge(v,u,0,-dis);
}
int level[maxn];
bool makelevel(int s,int t)
{
    queue<int>q;
    q.push(s);
    mem(level,0);
    level[s]=1;

    while(!q.empty())
    {
        int u=q.front();
        q.pop();
//        if(u==t)return 1;
        for(int i=head[u];i;i=edge[i].next)
        {
            int v=edge[i].v;
            int w=edge[i].w;
            if(level[v]==0&&w!=0)
            {
                level[v]=level[u]+1;
                q.push(v);
            }
        }
    }
    return level[t];
//    return level[t];
}
int dfs(int u,int flow,int t)
{
    if(u==t)return flow;
    int sum=0;
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].v;
        int w=edge[i].w;
        if(level[v]==level[u]+1&&w!=0)
        {
            int tmp=dfs(v,min(flow-sum,w),t);
            edge[i].w-=tmp;
            edge[i^1].w+=tmp;
            sum+=tmp;
            if(sum==flow)return sum;
        }
    }
    return sum;
}
int dinic()
{
    int ans=0;
    while(makelevel(S,T))
    {
        ans+=dfs(S,inf,T);
    }
    return ans;
}
int fa[maxn],vis[maxn],xb[maxn],flow[maxn];
inline bool spfa(int s,int t)
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    queue<int> q;
    while(!q.empty())
    q.pop();
    mem(fa,-1);
    vis[s]=1;dis[s]=0;fa[s]=0;
    flow[s]=inf;q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=edge[i].next)
        {
            int v=edge[i].v;
            if(edge[i].w>0&&dis[v]>dis[u]+edge[i].cost)
            {
                dis[v]=dis[u]+edge[i].cost;
                fa[v]=u;
                xb[v]=i;
                flow[v]=min(flow[u],edge[i].w);
                if(!vis[v]){vis[v]=1,q.push(v);}
            }
        }
    }
    return fa[t]!=-1;
}
inline int mcmf(int s,int t)
{
    int sum=0;
    while(spfa(s,t))
    {
        int k=t;
        while(k!=s)
        {
            edge[xb[k]].w-=flow[t];
            edge[xb[k]^1].w+=flow[t];
            k=fa[k];
        }
//        tot+=flow[t];
        sum+=flow[t]*dis[t];
    }
    return sum;
}
int main()
{
    cin>>n>>m>>k;
    S=1;T=n;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>uu[i]>>vv[i]>>ww[i]>>dis[i];
        add(uu[i],vv[i],ww[i],0);
    }
//    add(S,1,inf,0);
//    add(n,T,inf,0);
    cout<<dinic()<<" ";
    for(int i=1;i<=m;i++)
    {
        add(uu[i],vv[i],inf,dis[i]);
    }
    add(0,1,k,0);
    cout<<mcmf(0,n);

}

[ZJOI2010]网络扩容[网络流24题]

题意：

题解：

代码：