bzoj1834

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

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

#include
#include
#include
using namespace std;
const int inf=0x3f3f3f3f;
struct edge
{int to,nxt,f,c;
}e[10010];
int n,m,k,cnt=1,ans;
int g[10010],prev[10010],pree[10010],dist[10010],used[10010];
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,0,inf);
}
inline int Min(int x,int y)
{return xx:y; 
}
bool bfs()
{queue<int>q;memset(dist,inf,sizeof(dist));dist[1]=0;q.push(1);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]+1;q.push(v);}}}return dist[n]!=inf;
}
int dfs(int u,int delta)
{if(u==n) return delta;int ret=0;for(int i=g[u];i&δi=e[i].nxt){int v=e[i].to;if(dist[v]==dist[u]+1&&e[i].f){int dd=dfs(v,Min(e[i].f,delta));delta-=dd;e[i].f-=dd;e[i^1].f+=dd;            ret+=dd;}}return ret;
}
void spfa()
{queue<int>q;memset(dist,inf,sizeof(dist));memset(used,0,sizeof(used));dist[1]=0;q.push(1);while(!q.empty()){int u=q.front(); q.pop();used[u]=0;for(int i=g[u];i;i=e[i].nxt){int v=e[i].to;if((dist[v]>dist[u]&&e[i].f>0)||(dist[v]>dist[u]+e[i].c)&&e[i].f==0){if(e[i].f>0) dist[v]=dist[u];else dist[v]=dist[u]+e[i].c;prev[v]=u; pree[v]=i;if(!used[v]){used[v]=1;q.push(v);}}}}
}
int MinCost()
{int u=n,ret=0;while(u!=1){if(e[pree[u]].f>0) e[pree[u]].f--;u=prev[u];}return dist[n];
}
inline void MinCostFlow()
{ans=0;while(k--){spfa();ans+=MinCost();}printf("%d",ans);
}
inline void dinic()
{while(bfs()){ans+=dfs(1,inf);}printf("%d ",ans);
}
int main()
{scanf("%d%d%d",&n,&m,&k);for(int i=1;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 0;
}

转载于:https://www.cnblogs.com/19992147orz/p/6091443.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！