题解：UVA1486 Transportation

· · 题解

UVA1486 Transportation

解题思路

不难从题面看出，这是一个费用流的题目，但其又与费用流有一些差别。设一条边 e_i 的流量为 f_i，普通的费用流产生的费用为 w_i\times f_i，而在本题中为 w_i\times f_i^2。所以应当重新建图。

考虑拆边。原因很简单：因为一个 n 数的平方可以拆成长度为 n 且公差为 2 的等差序列的各项和，即

n^2=\sum \limits_{i=1}^{n} (2\times i-1)

我们可以将边 e_i 拆成 c_i 条边，每条边的容量为 1，第 j 条边的费用为 w_i\times(2\times j-1)，由于会求最小费用，必然会首先选择费用最小的边，这就保证了这条边的费用为 w_i\times f_i^2。

同时，由于题目中限制了最大流量为 k，因此要设立超级源点 S 和超级汇点 T，并 S 向 1 号点连边，n 号点向 T 连边，容量均为 k，且费用为 0。如果得出的最大流 f_{max}<k，则输出 -1。

完整代码

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
const int MAXN=5e4+5,oo=0x3f3f3f3f;
int n,m,k,s,t,h[MAXN],ec=1,ans,sum;
struct Edge{
    int u,v,w,c,nxt;
}e[MAXN<<2];
inline void AddEdge(int u,int v,int w,int c)
{
    e[++ec]={u,v,w,c,h[u]};
    h[u]=ec;
}
inline void Add(int u,int v,int w,int c)
{
    AddEdge(u,v,w,c);
    AddEdge(v,u,0,-c);
}
int vis[MAXN],dis[MAXN];
queue<int>que;
bool SPFA(int s,int t){ 
    while(!que.empty())que.pop();
    memset(vis,0,sizeof vis);
    memset(dis,0x3f,sizeof dis);
    vis[t]=1,que.push(t),dis[t]=0;
    while(!que.empty()){
        int u=que.front();que.pop();
        vis[u]=0;
        for(int i=h[u];i;i=e[i].nxt){
            if(e[i^1].w&&dis[u]+e[i^1].c<dis[e[i].v]){
                dis[e[i].v]=dis[u]+e[i^1].c;
                if(vis[e[i].v])continue;
                que.push(e[i].v);
                vis[e[i].v]=1;
            }
        }
    }
    return dis[s]!=oo;
} 
int DFS(int u, int t, int f){ 
    if(u==t||!f)return f;
    vis[u]=1;
    int rest=f;
    for(int i=h[u];i;i=e[i].nxt){
        if(dis[e[i].v]!=dis[u]-e[i].c||!e[i].w||vis[e[i].v])continue;
        int tmp=DFS(e[i].v,t,min(e[i].w,rest));
        if(!tmp){
            dis[e[i].v]=oo;
            continue;
        }
        e[i].w-=tmp;
        e[i^1].w+=tmp;
        rest-=tmp;
        if(!rest)return f;
    }
    vis[u]=0;
    return f-rest;
}
void ZKW(int s,int t){ 
    ans=sum=0;
    while(SPFA(s,t)){
        memset(vis,0,sizeof vis);
        int tmp=DFS(s,t,oo);
        ans+=tmp;sum+=tmp*dis[s];
    }
}
int main()
{
    while(~scanf("%d %d %d",&n,&m,&k)){
        memset(h,0,sizeof h);
        memset(e,0,sizeof e);
        ec=s=1,t=n;
        int S=0,T=n+1;
        for(int i=1,u,v,w,c;i<=m;i++)
        {
            scanf("%d %d %d %d",&u,&v,&c,&w);
            for(int j=1;j<=w;j++)Add(u,v,1,c*(j*2-1));
        }
        Add(S,s,k,0);
        Add(t,T,k,0);
        ZKW(S,T);
        if(ans>=k)printf("%d\n",sum);
        else puts("-1");
    }
    return 0;
}