第二道最小费用最大流，spfa+EK的组合比想象中快很多
开始开边表为点的8倍，RE,不知道为什么
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int maxn=508; const int INF=0x3f3f3f3f; struct fuck{ int u,v,cap,cost,next; }edge[maxn<<4]; int head[maxn]; int dis[maxn],pre[maxn],vis[maxn]; int tol; int n; void init() { tol=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int w,int c) { edge[tol].u=u; edge[tol].v=v; edge[tol].cap=c; edge[tol].cost=w; edge[tol].next=head[u]; head[u]=tol++; edge[tol].u=v; edge[tol].v=u; edge[tol].cap=0; edge[tol].cost=-w; edge[tol].next=head[v]; head[v]=tol++; } bool spfa() { queue<int> q; q.push(0); memset(dis,INF,sizeof(dis)); memset(vis,false,sizeof(vis)); dis[0]=0;vis[0]=true;pre[0]=-1; int i,u,v; while(!q.empty()) { u=q.front();q.pop(); vis[u]=false; for(i=head[u];i!=-1;i=edge[i].next) { v=edge[i].v; if(edge[i].cap>0&&dis[v]>dis[u]+edge[i].cost) { dis[v]=dis[u]+edge[i].cost; pre[v]=i; if(!vis[v]) q.push(v); } } } if(dis[n]>=INF) return false; return true; } int min_costflow() { int co,fl,u,i; co=fl=0; memset(dis,INF,sizeof(dis)); while(spfa()) { int mi=INF; bool flag=true; for(i=n;i!=0;i=edge[pre[i]].u) mi=min(mi,edge[pre[i]].cap); for(i=n;i!=0;i=edge[pre[i]].u) { edge[pre[i]].cap-=mi; edge[pre[i]^1].cap+=mi; } fl+=mi; co+=dis[n]; } return co; } int main() { int i,j,m,u,v,w,p; int cas=1; while(scanf("%d%d",&n,&m)==2) { init(); addedge(0,1,0,2); for(i=1;i<=m;i++) { scanf("%d%d%d%d",&u,&v,&w,&p); { addedge(u,v,w,1); addedge(u,v,w+p,1); } } addedge(n,n+1,0,2); n++; printf("Case %d: %d ",cas++,min_costflow()); } return 0; }