我借鉴了一些大神的代码也就是他们经常用的模板。。。
费用流模板
#include #include using namespace std;const int oo=1e9;const int mm=11111;const int mn=888;int node,src,dest,edge;int ver[mm],flow[mm],cost[mm],next[mm];int head[mn],dis[mn],p[mn],q[mn],vis[mn];/**这些变量基本与最大流相同，增加了cost 表示边的费用，p 记录可行流上节点对应的反向边*/void prepare(int _node,int _src,int _dest){ node=_node,src=_src,dest=_dest; for(int i=0; i =mn)?l=0:l) for(i=head[u=q[l]],vis[u]=0; i>=0; i=next[i]) if(flow[i]&&dis[v=ver[i]]>(tmp=dis[u]+cost[i])) { dis[v]=tmp; p[v]=i^1; if(vis[v])continue; vis[q[r++]=v]=1; if(r>=mn)r=0; } return p[dest]>-1;}/**源点到汇点的一条最短路即可行流，不断的找这样的可行流*/int SpfaFlow(){ int i,ret=0,delta; while(spfa()) { /**按记录原路返回求流量*/ for(i=p[dest],delta=oo; i>=0; i=p[ver[i]]) if(flow[i^1] =0; i=p[ver[i]]) flow[i]+=delta,flow[i^1]-=delta; ret+=delta*dis[dest]; } return ret;}
但是还有下面这个代码好像比上面的快一点。。。
#include #include using namespace std;const int oo=1e9;//无穷大const int maxm=1111111;//边的最大数量，为原图的两倍const int maxn=2222;//点的最大数量int node,src,dest,edge;//node节点数，src源点，dest汇点，edge边数int head[maxn],p[maxn],dis[maxn],q[maxn],vis[maxn];//head链表头，p记录可行流上节点对应的反向边，dis计算距离struct edgenode{ int to;//边的指向 int flow;//边的容量 int cost;//边的费用 int next;//链表的下一条边} edges[maxm];void prepare(int _node,int _src,int _dest);void addedge(int u,int v,int f,int c);bool spfa();inline int min(int a,int b){ return a =maxn)?l=0:1)) { for (i=head[u=q[l]],vis[u]=false; i!=-1; i=edges[i].next) { if (edges[i].flow&&dis[v=edges[i].to]>(tmp=dis[u]+edges[i].cost)) { dis[v]=tmp; p[v]=i^1; if (vis[v]) continue; vis[q[r++]=v]=true; if (r>=maxn) r=0; } } } return p[dest]>=0;}int spfaflow(){ int i,ret=0,delta; while (spfa()) { //按记录原路返回求流量 for (i=p[dest],delta=oo; i>=0; i=p[edges[i].to]) { delta=min(delta,edges[i^1].flow); } for (int i=p[dest]; i>=0; i=p[edges[i].to]) { edges[i].flow+=delta; edges[i^1].flow-=delta; } ret+=delta*dis[dest]; } return ret;}