bzoj1834

第一问很好搞。第二问事实上可以这么想。如果一条边的流量还有，那么我们走过去不要钱，否则要钱，于是跑个费用流，就好了

（其实跑k次spfa也可以，我是这么写的）

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

const int inf=0x3f3f3f3f;

struct edge

{

    int to,nxt,f,c;

}e[];

int n,m,k,cnt=,ans;

int g[],prev[],pree[],dist[],used[];

void link(int u,int v,int f,int c)

{

    e[++cnt].nxt=g[u];

    g[u]=cnt;

    e[cnt].to=v;

    e[cnt].f=f;

    e[cnt].c=c;

}

inline void ins(int u,int v,int f,int c)

{

    link(u,v,f,c); link(v,u,,inf);

}

inline int Min(int x,int y)

{

    return x<y?x:y;

}

bool bfs()

{

    queue<int>q;

    memset(dist,inf,sizeof(dist));

    dist[]=;

    q.push();

    while(!q.empty())

    {

        int u=q.front(); q.pop();

        for(int i=g[u];i;i=e[i].nxt)

        {

            int v=e[i].to;

            if(e[i].f&&dist[v]==inf)

            {

                dist[v]=dist[u]+;

                q.push(v);

            }

        }

    }

    return dist[n]!=inf;

}

int dfs(int u,int delta)

{

    if(u==n) return delta;

    int ret=;

    for(int i=g[u];i&&delta;i=e[i].nxt)

    {

        int v=e[i].to;

        if(dist[v]==dist[u]+&&e[i].f)

        {

            int dd=dfs(v,Min(e[i].f,delta));

            delta-=dd;

            e[i].f-=dd;

            e[i^].f+=dd;

            ret+=dd;

        }

    }

    return ret;

}

void spfa()

{

    queue<int>q;

    memset(dist,inf,sizeof(dist));

    memset(used,,sizeof(used));

    dist[]=;

    q.push();

    while(!q.empty())

    {

        int u=q.front(); q.pop();

        used[u]=;

        for(int i=g[u];i;i=e[i].nxt)

        {

            int v=e[i].to;

            if((dist[v]>dist[u]&&e[i].f>)||(dist[v]>dist[u]+e[i].c)&&e[i].f==)

            {

                if(e[i].f>) dist[v]=dist[u];

                else dist[v]=dist[u]+e[i].c;

                prev[v]=u;

                pree[v]=i;

                if(!used[v])

                {

                    used[v]=;

                    q.push(v);

                }

            }

        }

    }

}

int MinCost()

{

    int u=n,ret=;

    while(u!=)

    {

        if(e[pree[u]].f>) e[pree[u]].f--;

        u=prev[u];

    }

    return dist[n];

}

inline void MinCostFlow()

{

    ans=;

    while(k--)

    {

        spfa();

        ans+=MinCost();

    }

    printf("%d",ans);

}

inline void dinic()

{

    while(bfs())

    {

        ans+=dfs(,inf);

    }

    printf("%d ",ans);

}

int main()

{

    scanf("%d%d%d",&n,&m,&k);

    for(int i=;i<=m;i++)

    {

        int u,v,f,c; scanf("%d%d%d%d",&u,&v,&f,&c);

        ins(u,v,f,c);

    }

    dinic();

    MinCostFlow();

    return ;

}