普通最小费用流每条边的费用为flow*cost,此题限制为一个函数Fun(flow)*cost……
若Fun(flow)-Fun(flow-1)单调不减,可把边拆成(Fun(1)-Fun(0))*cost,(Fun(2)-Fun(1))*cost....(Fun(max)-Fun(max-1))*cost,此题即是,再加超级源限制总流量上界即可。
若Fun(flow)-Fun(flow-1)单调递减,可同上拆边,费用取负,加超级源限制总流量上界跑最小费用流即可。
若Fun(flow)-Fun(flow-1)不单调,私以为把距离扩成二维(flow,Fun(flow)-Fun(flow-1)),距离和为两个维度直接累加,比较时第一维优先。但这样似乎是错的,暂时没想到正解,求大神指导……
#include <algorithm> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <map> #include <set> #include <list> #include <stack> #include <queue> #include <deque> #include <vector> #include <string> #include <bitset> #include <memory> #include <complex> #include <numeric> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <time.h> #include <ctype.h> #include <locale.h> using namespace std; #pragma pack(4) const double eps = 1e-8; const double pi = acos(-1.0); const int inf = 0x7f7f7f7f; const __int64 INF = 0x7f7f7f7f7f7f7f7fll; #define at(a,i) ((a)&(1<<(i))) #define nt(a,i) ((a)^(1<<(i))) #define set1(a,i) ((a)|(1<<(i))) #define set0(a,i) ((a)&(~(1<<(i)))) #define gret(a,b) (((a)-(b))>eps) #define less(a,b) (((b)-(a))>eps) #define greq(a,b) (((a)-(b))>-eps) #define leeq(a,b) (((b)-(a))>-eps) #define equl(a,b) (fabs((a)-(b))<eps) #define lmax(a,b) ((a)>(b)?(a):(b)) #define lmin(a,b) ((a)<(b)?(a):(b)) #define fmax(a,b) (gret(a,b)?(a):(b)) #define fmin(a,b) (less(a,b)?(a):(b)) const int MAXV = 120; const int MAXE = 120000; struct node { int v,w,c; node(int _v=0,int _w=0,int _c=0): v(_v),w(_w),c(_c){} bool operator < (const node argu) const { return w<argu.w; } }G[MAXE]; int _index,pre[MAXV],next[MAXE]; void clear(void) { _index=0; memset(pre,-1,sizeof(pre)); } void add(int u,int v,int w=0,int c=0) { G[_index].v=v; G[_index].w=w; G[_index].c=c; next[_index]=pre[u]; pre[u]=_index++; G[_index].v=u; G[_index].w=0; G[_index].c=-c; next[_index]=pre[v]; pre[v]=_index++; } bool inQ[MAXV]; int dis[MAXV],Q[MAXV],prev[MAXV],curr[MAXV]; int SPFA(int src,int des) { int u,v,w; memset(dis,inf,sizeof(dis)); memset(inQ,false,sizeof(inQ)); Q[dis[src]=0]=src; for(int f=0,r=1;f!=r;f=(f+1)%MAXV) { inQ[u=Q[f]]=false; for(int i=pre[u];i!=-1;i=next[i]) { v=G[i].v; w=G[i].c; if(G[i].w&&dis[v]>dis[u]+w) { dis[v]=dis[u]+w; prev[v]=u; curr[v]=i; if(!inQ[v]) { inQ[Q[r]=v]=true; r=(r+1)%MAXV; } } } } return dis[des]; } int MinCost(int src,int des,int flow) { int cnt,sum=0,tot=0; while(SPFA(src,des)!=inf) { cnt=inf; for(int i=des;i!=src;i=prev[i]) { cnt=min(cnt,G[curr[i]].w); } for(int i=des;i!=src;i=prev[i]) { G[curr[i]].w-=cnt; G[curr[i]^1].w+=cnt; } sum+=(cnt*dis[des]); tot+=cnt; } return tot==flow?sum:-1; } int n,m,k,u,v,w,c; int main() { #ifndef ONLINE_JUDGE freopen("Transportation.txt","r",stdin); #endif while(scanf("%d %d %d",&n,&m,&k)!=EOF) { clear(); while(m--) { scanf("%d %d %d %d",&u,&v,&c,&w); for(int i=0;w>i;i++) { add(u,v,1,(2*i+1)*c); } } add(0,1,k,0); printf("%d\n",MinCost(0,n,k)); } return 0; }