//连续最短路径算法 //消圈算法 //先求最大流, 再在Gf中寻找负费用圈并沿它增广 //KM算法 //二分图的最优匹配 短距离图优势很大 //ZKW算法 //KM+SAP（Shortest Augmenting Path最短增广路） //原始对偶（Primal-Dual）算法 //S 源点 T汇点 n点的个数 struct node { int v;//该边连向的点 int f;//流量 int w;//权值 int next;//下一条边 }edge[Maxm] //有向边 注意一条边用两条边存 int head[n];//邻接表头数组 初始化为-1 int cnt; //建边计数器 初始化为0 int pre[n];//前驱数组 初始化为-1 int dis[n];//花费数组 类似最短路距离数组 bool vis[n];//标记数组 用于SPFA时记录是否访问过 bool spfa() //基于邻接表的SPFA算法 { int i; for(i=0; i<n; i++) //初始化 { pre[i]=-1; dis[i]=inf; vis[i]=false; } queue <int > q; dis[S]=0; vis[S]=true; q.push(S); while(!q.empty()) { int t=q.front(); q.pop(); i=head[t]; vis[t]=false; while(i!=-1) { if(edge[i].f>0&&dis[edge[i].v]>dis[t]+edge[i].w) { dis[edge[i].v]=dis[t]+edge[i].w; pre[edge[i].v]=i; if(!vis[edge[i].v]) { vis[edge[i].v]=true; q.push(edge[i].v); } } i=edge[i].next; } } if(pre[T]==-1)//如果不在最短路中 代表着最短路寻找失败 { return false; } return true; } int MinCostMaxFlow() { int ans=0; while(spfa()) //如果最短增广路寻找成功 { int max1=inf; int p=pre[T];//初始化P指针 while(p!=-1) //寻找关键流量 { max1=min(max1,edge[p].f); p=pre[edge[p].u]; } p=pre[T]; while(p!=-1) //修改流量 { edge[p].f-=max1; edge[p^1].f+=max1; ans+=max1*edge[p].w; p=pre[edge[p].u]; } } return ans; }
学长给的模板