UVALive-5095 Transportation (最小费用流+拆边)

时间:2024-10-09 14:37:39

题目大意:有n个点,m条单向边。要运k单位货物从1到n,但是每条道路上都有一个参数ai,表示经这条路运送x个单位货物需要花费ai*x*x个单位的钱。求最小费用。

题目分析:拆边。例如:u到v的容量为5,则拆成容量均为1,单位费用分别为1,3,5,7,9的5条边。求流恰好能满足运输需求时的最小费用即可。

代码如下:

# include<iostream>
# include<cstdio>
# include<cmath>
# include<string>
# include<vector>
# include<list>
# include<set>
# include<map>
# include<queue>
# include<cstring>
# include<algorithm>
using namespace std; # define LL long long
# define REP(i,s,n) for(int i=s;i<n;++i)
# define CL(a,b) memset(a,b,sizeof(a))
# define CLL(a,b,n) fill(a,a+n,b) const double inf=1e30;
const int INF=1<<30;
const int N=5005; int k; struct Edge
{
int fr,to,cap,fw,cost;
Edge(int fr,int to,int cap,int fw,int cost){
this->fr=fr;
this->to=to;
this->cap=cap;
this->fw=fw;
this->cost=cost;
}
};
struct MCMF
{
vector<Edge>edges;
vector<int>G[N];
int s,t,n;
int inq[N];
int p[N];
int a[N];
int d[N]; void init(int n,int s,int t)
{
this->n=n;
this->s=s,this->t=t;
for(int i=0;i<n;++i) G[i].clear();
edges.clear();
} void addEdge(int u,int v,int cap,int cost)
{
edges.push_back(Edge(u,v,cap,0,cost));
edges.push_back(Edge(v,u,0,0,-cost));
int m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
} bool bellmanFord(int &flow,int &cost)
{
fill(d,d+n,INF);
memset(inq,0,sizeof(inq));
d[s]=0,inq[s]=1,p[s]=0,a[s]=INF; queue<int>q;
q.push(s);
while(!q.empty())
{
int x=q.front();
q.pop();
inq[x]=0;
for(int i=0;i<G[x].size();++i){
Edge &e=edges[G[x][i]];
if(e.cap>e.fw&&d[e.to]>d[x]+e.cost){
d[e.to]=d[x]+e.cost;
p[e.to]=G[x][i];
a[e.to]=min(a[x],e.cap-e.fw);
if(!inq[e.to]){
inq[e.to]=1;
q.push(e.to);
}
}
}
}
if(d[t]==INF) return false;
flow+=a[t];
cost+=d[t]*a[t];
for(int u=t;u!=s;u=edges[p[u]].fr){
edges[p[u]].fw+=a[t];
edges[p[u]^1].fw-=a[t];
}
return true;
} void minCost(int &flow,int &cost)
{
flow=cost=0;
while(bellmanFord(flow,cost))
if(flow>=k) break;
}
};
MCMF cf; int n,m; int main()
{
while(~scanf("%d%d%d",&n,&m,&k))
{
cf.init(n+1,1,n);
int a,b,c,d;
while(m--)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
int cnt=1;
while(d--)
{
cf.addEdge(a,b,1,cnt*c);
cnt+=2;
}
}
int flow,cost;
cf.minCost(flow,cost);
if(flow>=k) printf("%d\n",cost);
else printf("-1\n");
}
return 0;
}