题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1834
做这个水题的过程可真是曲折
一开始我问camouflager跑个费用为0的费用流和跑个dinic差多少
讨论了一会结果是zkw费用流比较好
我就去看zkw费用流
然后发现大家都用邻接表
我怎么调也不太对
从早上一直到下午，最终放弃了zkw费用流，回归了单路增广
第一问跑一边最大流
第二问在原图的基础上，加上流量为k且有费用的原边
为了限制多出的流量为k，建一个超级源点，流量为最大流+k，费用为0
跑一边最小费用最大流
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
#include <bits/stdc++.h> #define MAXN 1010 #define MAXM 5050 #define pb push_back #define inf INT_MAX/2 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct node{ int from,to,num,cost; node(int a,int b,int c,int d){from=a,to=b;num=c;cost=d;} node(){} }edge[MAXM*4],edges[MAXM]; vector<int>v[MAXN]; int n,m,S,T,k,edgenum; int d[MAXN],dis[MAXN],pre[MAXN]; int Maxflow,Mincost; bool vis[MAXN]; inline void link(int x,int y,int z,int w){ edge[edgenum]=node(x,y,z,w); v[x].pb(edgenum++); edge[edgenum]=node(y,x,0,-w); v[y].pb(edgenum++); } inline bool spfa(){ fill(dis,dis+n+1,inf); memset(d,0,sizeof(d)); memset(vis,0,sizeof(vis)); queue<int>q; q.push(S); dis[S]=0; d[S]=1; vis[S]=1; while(!q.empty()){ int now=q.front(); q.pop(); if(now==T)continue; for(int i=0; i<v[now].size(); i++){ int j=v[now][i]; int to=edge[j].to; int cost=edge[j].cost; int num=edge[j].num; if(!num || dis[to]<=dis[now]+cost)continue; dis[to]=dis[now]+cost; d[to]=d[now]+1; pre[to]=j; if(!vis[to])q.push(to),vis[to]=1; } vis[now]=0; } return dis[T]!=inf; } inline void solve(){ Maxflow=0,Mincost=0; while(spfa()){ int Min=inf; for(int i=T; i!=S; i=edge[pre[i]].from)Min=min(Min,edge[pre[i]].num); for(int i=T; i!=S; i=edge[pre[i]].from)edge[pre[i]].num-=Min,edge[pre[i]^1].num+=Min; Maxflow+=Min; Mincost+=Min*dis[T]; } } int main(){ n=rd(),m=rd(),k=rd(); S=1,T=n; for(int i=1; i<=m; i++){ int x=rd(),y=rd(),z=rd(),w=rd(); edges[i]=node(x,y,z,w); link(x,y,z,0); } solve(); printf("%d ",Maxflow); edgenum=0; for(int i=S; i<=T; i++)v[i].clear(); for(int i=1; i<=m; i++){ link(edges[i].from,edges[i].to,edges[i].num,0); link(edges[i].from,edges[i].to,k,edges[i].cost); } S=0; link(S,1,Maxflow+k,0); solve(); printf("%d\n",Mincost); return 0; } |
