这题比较水，就是乱改改费用流模板。判断一下已经满流的边和没有满流的边，然后再改改最大流模板，然后把它们拼起来就是了。
话说这题第一遍90，然后撕烤一会发现自己yy的spfa扩容方式不允许反悔。然后改了一个貌似没什么用的地方，结果A了……
但是改的那个地方貌似是真的没什么用啊……
#include<cstdio> #include<cstdlib> #include<cctype> #include<algorithm> #include<cstring> #include<queue> #define maxn 2000 #define maxm 10000 using namespace std; inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } inline int count(int i){ return i&1?i+1:i-1; } struct Edge{ int from,next,to,dis,val,flow; }edge[maxm*2]; int head[maxn],num; inline void addedge(int from,int to,int dis,int val){ edge[++num]=(Edge){from,head[from],to,dis,val,0}; head[from]=num; } inline void add(int from,int to,int dis,int val){ addedge(from,to,dis,val); addedge(to,from,-dis,0); } int dfn[maxn]; bool vis[maxn]; int Start,End; int list[maxn]; bool bfs(){ memset(vis,0,sizeof(vis)); dfn[Start]=1; vis[Start]=1; queue<int>q; q.push(Start); while(!q.empty()){ int from=q.front();q.pop(); for(int i=head[from];i;i=edge[i].next){ int to=edge[i].to; if(edge[i].val==edge[i].flow||vis[to]) continue; vis[to]=1; dfn[to]=dfn[from]+1; q.push(to); } } return vis[End]; } int dfs(int x,int val){ if(x==End||val==0) return val; int flow=0; vis[x]=1; for(int &i=list[x];i;i=edge[i].next){ int to=edge[i].to; if(edge[i].val==edge[i].flow||vis[to]||dfn[to]!=dfn[x]+1) continue; int now=dfs(to,min(val,edge[i].val-edge[i].flow)); edge[i].flow+=now; edge[count(i)].flow-=now; val-=now; flow+=now; if(val<=0) break; } if(flow!=val) dfn[x]=-1; return flow; } int dis[maxn]; int pre[maxn]; int spfa(){ memset(dis,127/3,sizeof(dis)); dis[Start]=0; memset(vis,0,sizeof(vis)); queue<int>q; q.push(Start); while(!q.empty()){ int from=q.front(); q.pop(); vis[from]=0; for(int i=head[from];i;i=edge[i].next){ int to=edge[i].to; if(edge[i].val>edge[i].flow){ if(dis[to]<=dis[from]) continue; dis[to]=dis[from]; } else{ if(edge[i].dis<0) continue; if(dis[to]<=dis[from]+edge[i].dis) continue; dis[to]=dis[from]+edge[i].dis; } pre[to]=i; if(vis[to]) continue; vis[to]=1; q.push(to); } } int now=End; while(now!=Start&&now){ int ret=pre[now]; if(edge[ret].val==edge[ret].flow) edge[ret].val++; edge[ret].flow++; edge[count(ret)].flow--; now=edge[ret].from; } return dis[End]; } int main(){ int n=read(),m=read(),e=read();End=n;Start=1; for(int i=1;i<=m;++i){ int a=read(),b=read(),c=read(),d=read(); add(a,b,d,c); } int ans=0; while(bfs()){ memset(vis,0,sizeof(vis)); for(int i=1;i<=n;++i) list[i]=head[i]; int now=dfs(Start,0x7fffffff); if(!now) break; ans+=now; } printf("%d",ans); long long now=0; for(int i=1;i<=e;++i) now+=spfa(); printf(" %lld",now); return 0; }