本文主要是介绍uva1349 Optimal Bus Route Design 费用流，二分图匹配，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：n个景点和一些路径，找到任意数目的路径，路径是一个环，使每个景点仅属于一个环，使权值最小。
分析：每个景点的入度和出度都是1，拆分每个景点u，u'，若输入u-v，建立u-v'的边，是一个二分图，若存在完美匹配，说明存在若干个环使每个景点属于其中一个环。增加一个起点s和终点t，边权为费用，所有边的容量都为1，求最小费用最大流，若flow==节点数，存在完美匹配，cost即为答案。
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#define inf 10000000
#define pi acos(-1.0)
#define eps 1e-8
#define seed 131
using namespace std;
typedef pair<int,int> pii;
typedef unsigned long long ULL;
typedef long long LL;
const int maxn=100005;
struct Edge
{int from,to,cap,flow,cost;Edge(){}Edge(int a,int b,int c,int d,int e):from(a),to(b),cap(c),flow(d),cost(e){}
}edge[maxn];
int head[200];
int next[maxn];
int g[200];
int e,n;
void addEdge(int a,int b,int c)
{edge[e]=Edge(a,b,1,0,c);next[e]=head[a];head[a]=e++;edge[e]=Edge(b,a,0,0,-c);next[e]=head[b];head[b]=e++;
}
bool solve(int s,int t,int& flow,int& cost)
{bool vis[200];memset(vis,0,sizeof(vis));int pre[200];int d[200];int a[200];queue<int>que;que.push(0);vis[0]=1;for(int i=0;i<=t;i++)d[i]=inf;d[0]=0;a[0]=inf;while(!que.empty()){int u=que.front();que.pop();vis[u]=0;for(int i=head[u];i!=-1;i=next[i]){Edge& ed=edge[i];if(ed.cap>ed.flow&&d[ed.to]>d[u]+ed.cost){d[ed.to]=d[u]+ed.cost;pre[ed.to]=i;a[ed.to]=min(a[u],ed.cap-ed.flow);if(vis[ed.to]==0){que.push(ed.to);vis[ed.to]=1;}}}}if(d[t]==inf)return false;flow+=a[t];cost+=a[t]*d[t];for(int i=t;i!=s;i=edge[pre[i]].from){edge[pre[i]].flow+=a[t];edge[pre[i]^1].flow-=a[t];}return true;
}
int main()
{int a,b;int s,t;while(~scanf("%d",&n)){if(n==0)break;for(int i=1;i<=n;i++)g[i]=n+i;memset(head,-1,sizeof(head));e=0;for(int i=1;i<=n;i++){while(scanf("%d",&a)){if(a==0)break;scanf("%d",&b);addEdge(i,g[a],b);}}s=0;t=2*n+1;for(int i=1;i<=n;i++){addEdge(s,i,0);addEdge(g[i],t,0);}int flow=0,cost=0;while(solve(s,t,flow,cost));if(flow==n)printf("%d\n",cost);elseprintf("N\n");}return 0;
}这篇关于uva1349 Optimal Bus Route Design 费用流，二分图匹配的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
