题目链接：

比赛的时候，准备用最短路来做，存两张图，做两次最短路，本来还觉得第二张图的设计很好的，很不错，结果过了好多案例，还是莫名其妙的WA了。

好吧，问题来了。

6 7

1 2 1 100

2 3 10 100

1 4 10 100

2 5 1 100

3 6 10 100

4 5 10 100

5 6 1 100

ans = 42,

最短路思路就是不对的。

完了之后，听阳哥说，直接MCMF啊，当时我就傻逼了，主要是我MCMF的题目做少了，不会想到是MCMF。

这里： 每条边的容量是1，花费是边权，然后是超级源点和汇点，容量是2，花费是0。

模板来自刘汝佳，改了Bellman-Ford,用的是SPFA.

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define INF 0x3f3f3f3fusing namespace std;const int maxn = 600;struct Edge{    int from,to,cap,flow,cost;    Edge() {}    Edge(int a,int b,int c,int d,int e):from(a),to(b),cap(c),flow(d),cost(e) {}};struct MCMF{    int n,m,s,t;    vector
          
            edges; vector
           
             g[maxn]; int inq[maxn]; int d[maxn]; int p[maxn]; int a[maxn]; void init(int n) { this->n =n; for(int i=0; i
            

q; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); inq[u]=0; for(int i=0; i

e.flow && d[e.to]>d[u]+e.cost) { d[e.to]=d[u]+e.cost; p[e.to]=g[u][i]; a[e.to]=min(a[u],e.cap-e.flow); if(!inq[e.to]) { q.push(e.to); inq[e.to]=1; } } } } if(d[t]==INF) return false; flow+=a[t]; cost+=a[t]*d[t]; for(int u=t; u!=s; u=edges[p[u]].from) { edges[p[u]].flow +=a[t]; edges[p[u]^1].flow-=a[t]; } return true; } int MincostMaxflow(int s,int t) { int flow=0,cost =0; while(spfa(s,t,flow,cost)); return cost; }} sol;int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); int n,m,cas=1; while(scanf("%d%d",&n,&m)!=EOF) { int s=0,t=n+1; sol.init(n+2); while(m--) { int u,v,c,ad; scanf("%d%d%d%d",&u,&v,&c,&ad); sol.addedge(u,v,1,c); sol.addedge(u,v,1,c+ad); } sol.addedge(s,1,2,0); sol.addedge(n,t,2,0); printf("Case %d: %d\n",cas++,sol.MincostMaxflow(s,t)); }}