第一问直接板子敲上去
第二问并不明白直接在残量网络上加边的神仙做法
非常显然我们需要让流量加\(k\)，那么我们就使得网络里的总流量为\(maxf+k\)，\(maxf\)是第一问求出来的最大流
所以搞一个超级源点，向\(1\)连一条流量是\(maxf+k\)费用是\(0\)的边，之后在原来的图的基础上再给每条边加一条流量为\(inf\)，费用为相应费用的边
这样让它自己在里面流就必然会流出来\(maxf+k\)的流量
求出最小费用就好了
代码
#include#include #include #include #include #define maxn 1005#define re register#define LL long long#define inf 999999999#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read(){ char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar(); return x;}struct E{int v,nxt,w,f;} e[20005];int d[maxn],vis[maxn],head[maxn];int n,m,num=1,K,S,T;int a[5005],b[5005],c[5005],t[5005];inline void add(int x,int y,int ca,int z){e[++num].v=y;e[num].nxt=head[x];e[num].f=ca,e[num].w=z;head[x]=num;}inline void C(int x,int y,int ca,int z){add(x,y,ca,z),add(y,x,0,-1*z);}inline int SPFA(){ std::queue q; for(re int i=S;i<=T;i++) d[i]=inf,vis[i]=0; d[T]=0,vis[T]=1,q.push(T); while(!q.empty()) { int k=q.front();q.pop();vis[k]=0; for(re int i=head[k];i;i=e[i].nxt) if(e[i^1].f&&d[e[i].v]>d[k]+e[i^1].w) { d[e[i].v]=d[k]+e[i^1].w; if(!vis[e[i].v]) vis[e[i].v]=1,q.push(e[i].v); } } return d[S]