CSU1506 最小费用最大流

题目大意：给你一张图，一个人走过之后路径的费用会增加，问有2个人走，最小的总费用是多少。

算法思路：一开始准备跑2遍dijkstra，每次求最小的费用，不知道为什么这样一直WA，最后问了一下别人，发现是用最小费用最大流，每个点之间连接2条边，一条是走之前正常的路，另一条是走完这条路后增加了费用的路，因为有2个人，因此超级源点与起点的容量为2，超级汇点与终点的容量为2，跑一遍最小费用最大流的模板就可以。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
#define MAXN 10000
#define MAXM 100000
#define INF 0x3f3f3f3f
struct Edge
{
    int u;
    int v;
    int cap;
    int cost;
    int flow;
};
Edge edges[MAXM];
int n,m,a,b,c,add,e,ans,s,t;
int pre[MAXN];
int head[MAXN],nnext[MAXM],dist[MAXN];
bool visited[MAXN];
void addEdge(int u,int v,int cap,int cost)
{

    edges[e].v=v;
    edges[e].cap=cap;
    edges[e].cost=cost;
    edges[e].flow=0;
    nnext[e]=head[u];
    head[u]=e++;

    edges[e].v=u;
    edges[e].cap=0;
    edges[e].cost=-cost;
    edges[e].flow=0;
    nnext[e]=head[v];
    head[v]=e++;
}
bool spfa(int src, int x)
{
    queue<int>q;
    for(int i = src; i <=x; i++)
    {
        dist[i] = INF;
        visited[i] = false;
        pre[i] = -1;
    }
    dist[src] = 0;
    visited[src] = true;
    q.push(src);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        visited[u] = false;
        for(int i = head[u]; i!=-1; i=nnext[i])
        {
            int v = edges[i].v;
            if(edges[i]. cap > edges[i].flow &&
                    dist[v] > dist[u] + edges[i].cost )
            {
                dist[v] = dist[u] + edges[i].cost;
                pre[v] = i;
                if(!visited[v])
                {
                    visited[v] = true;
                    q.push(v);
                }
            }
        }
    }
    if(pre[x] == -1)
        return false;
    return true;
}
int min_cost_max_flow()
{
    int minflow=0;
    while(spfa(s,t))
    {
        int sum=INF,p=0;
        for(int i=pre[t]; i+1; i=pre[edges[i^1].v])
        {
            sum=min(sum,edges[i].cap-edges[i].flow);
        }

        for(int i=pre[t]; i+1; i=pre[edges[i^1].v])
        {
            edges[i].flow+=sum;
            edges[i^1].flow-=sum;
            ans+=sum*edges[i].cost;

        }
        minflow+=sum;

    }
    return ans;
}
int main()
{

    int cas=0;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        cas++;
        e=0;
        ans=0;
        memset(head,-1,sizeof(head));
        memset(nnext,-1,sizeof(nnext));
        s=0;
        t=n+1;

        for(int i=1; i<=m; i++)
        {
            scanf("%d%d%d%d",&a,&b,&c,&add);
            addEdge(a,b,1,c);
            addEdge(a,b,1,c+add);
        }
        addEdge(s,1,2,0);
        addEdge(n,t,2,0);
        printf("Case %d: %d\n",cas,min_cost_max_flow());

    }



    return 0;
}