首页 > 代码库 > 【网络流#9】POJ 2135 Farm Tour 最小费用流 - 《挑战程序设计竞赛》例题
【网络流#9】POJ 2135 Farm Tour 最小费用流 - 《挑战程序设计竞赛》例题
【题意】给出一张无向图，从1开始到n，求两条没有公共边的最短路，使得路程总和最小
每条边的权值设为费用，最大流量设为1，然后就是从源点到汇点流量为2的最小费用流。
因为是规定了流量，新建一个源点和一个汇点，源点到结点1连一条最大流量为2，费用为0的边，结点N到汇点连一条最大流量为2，费用为0的边，这样就规定好流量了。
#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>#include<set>#include<map>#include<stack>#include<vector>#include<queue>#include<string>#include<sstream>#define eps 1e-9#define ALL(x) x.begin(),x.end()#define INS(x) inserter(x,x.begin())#define FOR(i,j,k) for(int i=j;i<=k;i++)#define MAXN 1005#define MAXM 40005#define INF 0x3fffffffusing namespace std;typedef long long LL;int i,j,k,n,m,x,y,ans,big,cas,num,w,t,u,v,S,T;bool flag;int head[MAXN],vis[MAXN],dis[MAXN],pos[MAXN],Edge,size;char s[305][305];struct edgenode{ int to,next,w,cost;} edge[MAXM]; void add_edge(int x,int y,int w,int cost){ edge[Edge].to=y; edge[Edge].w=w; edge[Edge].cost=cost; edge[Edge].next=head[x]; head[x]=Edge; Edge++; edge[Edge].to=x; edge[Edge].w=0; edge[Edge].cost=-cost; edge[Edge].next=head[y]; head[y]=Edge; Edge++;} bool SPFA(int s, int t){ int u,v,i; queue <int> q; memset(vis,0,sizeof(vis)); for(i=0;i<size;i++) dis[i]=INF; dis[s]=0; vis[s]=1; q.push(s); while(!q.empty()) { u=q.front(); q.pop(); vis[u]=0; for (i=head[u];i!=-1;i=edge[i].next) { v=edge[i].to; if(edge[i].w>0&&dis[u]+edge[i].cost<dis[v]) { dis[v]=dis[u]+edge[i].cost; pos[v]=i; if(!vis[v]) { vis[v]=1; q.push(v); } } } } return dis[t]!=INF;}int MinCostFlow(int s,int t){ int i,cost=0,flow=0; while(SPFA(s,t)) { int d=INF; for (i=t;i!=s;i=edge[pos[i]^1].to) { d=min(d,edge[pos[i]].w); } for(i=t;i!=s;i=edge[pos[i]^1].to) { edge[pos[i]].w-=d; edge[pos[i]^1].w+=d; } flow+=d; cost+=dis[t]*d; } return cost; // flow是最大流值}int main(){ memset(head,-1,sizeof(head));Edge=0; scanf("%d%d",&n,&m); for (i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&t); add_edge(x,y,1,t); add_edge(y,x,1,t); } S=0;T=n+1; size=n+2; add_edge(S,1,2,0); add_edge(n,T,2,0); printf("%d\n",MinCostFlow(S,T)); return 0;}
【网络流#9】POJ 2135 Farm Tour 最小费用流 - 《挑战程序设计竞赛》例题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。