第二道最小费用最大流，spfa+EK的组合比想象中快很多
开始开边表为点的8倍，RE,不知道为什么
#include#include #include #include 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 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\n",cas++,min_costflow()); } return 0;}