【题目大意】
给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求： 1、 在不扩容的情况下，1到N的最大流； 2、 将1到N的最大流增加K所需的最小扩容费用。
【思路】
问题用Dinic搞一搞。问题二可以看出是费用流。
(1)残余网络中边还有一些容量，而如果利用这些容量，是不需要花费新的费用的。则将这些边的费用设置为0。
(2)对于原有的边，添加一条起点、终点相同的点，容量设置为INF，费用设置为一开始输入的扩容费用。再添加一个超级源点，和1之间添加一条边，容量为K，费用为0。
所谓的费用流，就是将EK中每一次搜索改为关于单位费用的SPFA即可，其余板块类似。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int MAXN=+;
const int MAXM=+;
const int INF=0x7fffffff;
int n,m,k;//点数边数和需要扩充的容量
struct node
{
int to,cap,pos,w;
};
vector<node> E[MAXN];
int vis[MAXN];
int dis[MAXN];
int U[MAXM],V[MAXM],C[MAXM],W[MAXM];
int pre[MAXN],preedge[MAXN];//记录每次SPFA中每一个节点的前驱,以及当前节点在前驱的vector中是第几条边 void addedge(int u,int v,int c,int w)
{
E[u].push_back((node){v,c,E[v].size(),w});
E[v].push_back((node){u,,E[u].size()-,-w});/*失误把这里敲成了E[u]，看了好久才看出来T T*/
} void init()
{
scanf("%d%d%d",&n,&m,&k);
for (int i=;i<m;i++)
{
scanf("%d%d%d%d",&U[i],&V[i],&C[i],&W[i]);
addedge(U[i],V[i],C[i],);
}
} int bfs()
{
queue<int> que;
memset(dis,-,sizeof(dis));
dis[]=;
que.push();
while (!que.empty())
{
int head=que.front();que.pop();
for (int i=;i<E[head].size();i++)
{
node tmp=E[head][i];
if (dis[tmp.to]==- && tmp.cap>)
{
dis[tmp.to]=dis[head]+;
que.push(tmp.to);
}
}
}
if (dis[n]==-) return ;
else return ;
} int dfs(int s,int e,int f)
{
vis[s]=;
if (s==e) return f;
for (int i=;i<E[s].size();i++)
{
node& tmp=E[s][i];
if (!vis[tmp.to] && tmp.cap> && dis[tmp.to]==dis[s]+)
{
int delta=dfs(tmp.to,e,min(f,tmp.cap));
if (delta>)
{
tmp.cap-=delta;
E[tmp.to][tmp.pos].cap+=delta;
return delta;
}
}
}
return ;
} void dinic()
{
int flow=;
while (bfs())
{
memset(vis,,sizeof(vis));
int f=dfs(,n,INF);
if (f==) break;
else flow+=f;
}
cout<<flow<<' ';
} void rebuild()
{
for (int i=;i<m;i++) addedge(U[i],V[i],INF,W[i]);
addedge(,,k,);
} int spfa(int u,int v)
{
memset(vis,,sizeof(vis));
for (int i=;i<=n;i++) dis[i]=INF;
memset(pre,-,sizeof(pre));
queue<int> que;
dis[]=;
vis[]=;
que.push();
while (!que.empty())
{
int head=que.front();
que.pop();
vis[head]=;
for (int i=;i<E[head].size();i++)
{
node& tmp=E[head][i];
if (tmp.cap> && dis[tmp.to]>dis[head]+tmp.w)
{
dis[tmp.to]=dis[head]+tmp.w;
pre[tmp.to]=head;
preedge[tmp.to]=i;
if (!vis[tmp.to])
{
vis[tmp.to]=;
que.push(tmp.to);
}
}
}
}
if (dis[n]==INF) return ;
else return ;
} void mcf()
{
int ans=;
while (spfa(,n))
{
int flow=INF;
for (int i=n;pre[i]!=-;i=pre[i])
flow=min(flow,E[pre[i]][preedge[i]].cap);
for (int i=n;pre[i]!=-;i=pre[i])
{
node& tmp=E[pre[i]][preedge[i]];
tmp.cap-=flow;
E[tmp.to][tmp.pos].cap+=flow;
ans+=flow*tmp.w;
}
}
cout<<ans<<endl;
} int main()
{
init();
dinic();
rebuild();
mcf();
return ;
}