首页 > 代码库 > POJ 2195 地图的最小费用最大流
POJ 2195 地图的最小费用最大流
思路:这题刚开始看就知道是最小费用最大流了,因为求出最优嘛,而且要m,H要一一对应,所以不是二分图匹配就是最小费用最大流。
不过,刚开始还在想每个m与H之间的最小花费如何求,难道要用dfs搜索吗?这样想之后看了下题目给的时间是1000ms,然后就把dfs搜索m与H之间的最短距离排除了。然后想了想,其实尼玛太简单了,因为题目说了只能垂直与竖直的走,所以最短距离不就是两个横坐标相减与两个纵坐标相减之和嘛!
然后每对m与H之间都连边,流量为1(因为每对匹配不能重复),费用为它们之间的距离即花费;然后建超级源点和超级汇点,源点和每个m相连,流量和上面一样也是1(单一匹配嘛),费用为0,因为它们之间不产生花费;汇点和源点建边一样。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<queue> #include<set> #include<cmath> #include<bitset> #define mem(a,b) memset(a,b,sizeof(a)) #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r #define llson j<<1,l,mid #define rrson j<<1|1,mid+1,r #define INF 0x7fffffff typedef long long ll; typedef unsigned long long ull; using namespace std; #define maxn 20005 struct { int v,w,c,next,re; //re记录逆边的下标,c是费用,w是流量 } e[maxn]; int n,cnt; int head[maxn],que[maxn*8],pre[maxn],dis[maxn]; bool vis[maxn]; void add(int u, int v, int w, int c) { e[cnt].v=v,e[cnt].w=w,e[cnt].c=c; e[cnt].next=head[u]; e[cnt].re=cnt+1,head[u]=cnt++; e[cnt].v=u,e[cnt].w=0,e[cnt].c=-c; e[cnt].next=head[v]; e[cnt].re=cnt-1,head[v]=cnt++; } bool spfa() { int i, l = 0, r = 1; for(i = 0; i <= n; i ++) dis[i] = INF,vis[i] = false; dis[0]=0,que[0]=0,vis[0]=true; while(l<r) { int u=que[l++]; for(i=head[u];i!=-1;i=e[i].next) { int v = e[i].v; if(e[i].w&&dis[v]>dis[u]+e[i].c) { dis[v] = dis[u] + e[i].c; pre[v] = i; if(!vis[v]) { vis[v] = true; que[r++] = v; } } } vis[u] = false; } return dis[n]!=INF; } int change() { int i,p,sum=INF,ans=0; for(i=n;i!=0;i=e[e[p].re].v) {//e[e[p].re].v为前向结点,不理解看add和spfa p=pre[i];//p为前向结点编号 sum=min(sum,e[p].w); } for(i=n;i!=0;i=e[e[p].re].v) { p=pre[i]; e[p].w-=sum; e[e[p].re].w+=sum; ans+=sum*e[p].c;//c记录的为单位流量费用,必须得乘以流量。 } return ans; } int EK() { int sum=0; while(spfa()) sum+=change(); return sum; } void init() { mem(head,-1),mem(pre,0),cnt=0; } char s[102][102]; struct mm { int x,y; }mm[101],hh[101]; int main() { //freopen("1.txt","r",stdin); int N,M; while(~scanf("%d%d",&N,&M)) { if(!N&&!M) break; int i,j,tot=0,tmp=0,dist; init(); for(i=0;i<N;i++) { scanf("%s",s[i]); for(j=0;j<M;j++) { if(s[i][j]=='m') mm[tot].x=i,mm[tot++].y=j; if(s[i][j]=='H') hh[tmp].x=i,hh[tmp++].y=j; } } n=tot+tmp+1; for(i=1;i<=tot;i++) add(0,i,1,0);//因为每条边只能用一次,所以流量为1 for(i=tot+1;i<=tot+tmp;i++) add(i,n,1,0);//因为每条边只能用一次,所以流量为1 for(i=1;i<=tot;i++) for(j=tot+1;j<=tot+tmp;j++) { dist=abs(mm[i-1].x-hh[j-tot-1].x)+abs(mm[i-1].y-hh[j-tot-1].y); add(i,j,1,dist);//费用为m与H的最短距离即最小花费 } printf("%d\n",EK()); } return 0; }
POJ 2195 地图的最小费用最大流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。