HDOJ 3667 Transportation 最小费用最大流+拆边+加点
这个题，是我第一次试着自己理解模板，理解题意去做题
先说题意：提到了边上的费用，提到了运送物品的数目，最后问的是，要运送k个物品求的最小花费
这个没说的，肯定是用最小费用最大流的模板搞
问题一：
费用边怎么加？
题目中说的：运送x的物品，那么付费是c*x*x，意思是跟物品的重量不成正比，而模板中是成正比的，怎么办？
观察到一个细节：c不超过5！那么我们可以把本来容量为c的边拆成c条容量为1的边，让路上的付费权重不一样就好了
第一条边权重为1，第二条为3，第三条为5，第四条为7，第五条为9（最多5条边）
问题二：
这个题：不是求最大流啊！是流量到了K就已经够了！
方法一：改成最大流模型！添加一个源点，添加一个汇点，源点向1连边容量为K，费用为0；n向汇点连边，容量为K，费用为0
那么就搞定了，跑模板就好了
方法二：注意这个题的特殊性！
每条边的容量都是1！那么在找增广路的时候，如果能够找到至少K条，由于是最小费用最大流的模板，那么我们取前K条就好了，提前判断退出就可以了
下面把两个代码都贴出来：
方法一还是比较通用的代码吧，是用网络流的思路在思考题目：
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<queue>
using namespace std;
const int maxn=10000;
const int maxm=300000;
const int inf=0x3f3f3f3f;
struct Edge{
int to,nxt,cap,flow,cost;
}edge[maxm];
int Head[maxn],tol;
int pre[maxn];
int dis[maxn];
bool vis[maxn];
int N;
int n,m,k;
void init(int n){
tol=0;
memset(Head,-1,sizeof(Head));
}
void addedge(int u,int v,int cap,int cost){
edge[tol].to=v;
edge[tol].cap=cap;
edge[tol].cost=cost;
edge[tol].flow=0;
edge[tol].nxt=Head[u];
Head[u]=tol++;
edge[tol].to=u;
edge[tol].cap=0;
edge[tol].cost=-cost;
edge[tol].flow=0;
edge[tol].nxt=Head[v];
Head[v]=tol++;
}
bool spfa(int s,int t){
queue<int> q;
for(int i=0;i<=n+1;i++){
dis[i]=inf;
vis[i]=false;
pre[i]=-1;
}
dis[s]=0;
vis[s]=true;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=false;
for(int i=Head[u];i!=-1;i=edge[i].nxt){
int v=edge[i].to;
if (edge[i].cap>edge[i].flow&&dis[v]>dis[u]+edge[i].cost){
dis[v]=dis[u]+edge[i].cost;
pre[v]=i;
if (!vis[v]){
vis[v]=true;
q.push(v);
}
}
}
}
if (pre[t]==-1) return false;
return true;
}
int minCostMaxflow(int s,int t,int &cost){
int flow=0;
cost=0;
while(spfa(s,t)){
int Min=inf;
for(int i=pre[t];i!=-1;i=pre[edge[i^1].to])
if (Min>edge[i].cap-edge[i].flow)
Min=edge[i].cap-edge[i].flow;
for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]){
edge[i].flow+=Min;
edge[i^1].flow-=Min;
cost+=edge[i].cost*Min;
}
flow+=Min;
}
return flow;
}
int main(){
//freopen("input.txt","r",stdin);
while(scanf("%d%d%d",&n,&m,&k)!=EOF){
init(n+2);
int u,v,c,a;
while(m--){
scanf("%d%d%d%d",&u,&v,&a,&c);
for(int i=1;i<=c;i++)
addedge(u,v,1,a*(2*i-1));
}
addedge(0,1,k,0);
addedge(n,n+1,k,0);
a=0;
c=minCostMaxflow(0,n+1,a);
if (c<k) puts("-1");
else printf("%d\n",a);
}
return 0;
}方法二的思考方向是针对这个题的特点来搞的，由于建图很特殊，每条边的容量都是1：
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<queue>
using namespace std;
const int maxn=10000;
const int maxm=300000;
const int inf=0x3f3f3f3f;
struct Edge{
int to,nxt,cap,flow;
long long cost;
}edge[maxm];
int Head[maxn],tol;
int pre[maxn];
long long dis[maxn];
bool vis[maxn];
int N;
int n,m,k;
void init(int n){
N=n;
tol=0;
memset(Head,-1,sizeof(Head));
}
void addedge(int u,int v,int cap,long long cost){
edge[tol].to=v;
edge[tol].cap=cap;
edge[tol].cost=cost;
edge[tol].flow=0;
edge[tol].nxt=Head[u];
Head[u]=tol++;
edge[tol].to=u;
edge[tol].cap=0;
edge[tol].cost=-cost;
edge[tol].flow=0;
edge[tol].nxt=Head[v];
Head[v]=tol++;
}
bool spfa(int s,int t){
queue<int> q;
for(int i=1;i<=N;i++){
dis[i]=inf;
vis[i]=false;
pre[i]=-1;
}
dis[s]=0;
vis[s]=true;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=false;
for(int i=Head[u];i!=-1;i=edge[i].nxt){
int v=edge[i].to;
if (edge[i].cap>edge[i].flow&&dis[v]>dis[u]+edge[i].cost){
dis[v]=dis[u]+edge[i].cost;
pre[v]=i;
if (!vis[v]){
vis[v]=true;
q.push(v);
}
}
}
}
if (pre[t]==-1) return false;
return true;
}
int minCostMaxflow(int s,int t,long long &cost){
bool flag=false;
int flow=0;
cost=0;
while(spfa(s,t)&&flow<k){
int Min=inf;
for(int i=pre[t];i!=-1;i=pre[edge[i^1].to])
if (Min>edge[i].cap-edge[i].flow)
Min=edge[i].cap-edge[i].flow;
for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]){
edge[i].flow+=Min;
edge[i^1].flow-=Min;
cost+=edge[i].cost*Min;
}
flow+=Min;
}
return flow;
}
int main(){
//freopen("input.txt","r",stdin);
while(scanf("%d%d%d",&n,&m,&k)!=EOF){
init(n);
int u,v,c;
long long a;
while(m--){
scanf("%d%d%lld%d",&u,&v,&a,&c);
for(int i=1;i<=c;i++)
addedge(u,v,1,a*(2*i-1));
}
a=0;
c=minCostMaxflow(1,n,a);
if (c<k) puts("-1");
else printf("%lld\n",a);
}
return 0;
}
好未来公司福利 52人发布