最小费用最大流,即MCMF(Minimum Cost Maximum Flow)问题
嗯~第一次写费用流题。。。
这道就是费用流的模板题,找不到更裸的题了
建图:每个m(Man)作为源点,每个H(House)作为汇点,各个源点与汇点分别连一条边,这条边的流量是1(因为每个源点只能走一条边到汇点),费用是 从源点走到汇点的步数,因为有多个源点与汇点,要建一个超级源点与超级汇点,超级源点与各个源点连一条流量为1,费用为0(要避免产生多余的费用)的边
按照这个图跑一发费用流即可
关于模板:前向星+SPFA
初始化注意:size 表示网络中的结点数,编号从0开始,如果是从1开始则size=n+1,其他的,head全设为-1,Edge为边数预先设为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 MAXN 3000 #define MAXM 50000 #define INF (1<<30) #define eps 0.000001 #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) using namespace std; int i,j,k,n,m,x,y,T,num,w,Man,House,hou[305][2],man[305][2]; /*最小费用流模板 -BEGIN-*/ /*size表示网络中的结点数,编号从0开始,如果是从1开始则size=n+1*/ /*初始化:head全设为-1,Edge为边数预先设为0*/ 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是最大流值 } /*最小费用流模板 -END-*/ int main() { while(scanf("%d%d",&n,&m),n+m) { memset(head,-1,sizeof(head)); Edge=Man=House=num=0; for (i=0;i<n;i++) scanf("%s",s[i]); for (i=0;i<n;i++) { for (j=0;j<m;j++) { if (s[i][j]=='m') { Man++; man[Man][0]=i; man[Man][1]=j; }else if (s[i][j]=='H') { House++; hou[House][0]=i; hou[House][1]=j; } } } size=Man+House+2; /*超级源点0,到各个人的边*/ for (i=1;i<=Man;i++) { add_edge(0,i,1,0); } /*各源点与各汇点之间的边*/ for (i=1;i<=Man;i++) { for (j=1;j<=House;j++) { add_edge(i,Man+j,1,abs(man[i][0]-hou[j][0])+abs(man[i][1]-hou[j][1])); } } /*超级汇点0,到各个人的边*/ for (i=1;i<=House;i++) { add_edge(Man+i,Man+House+1,1,0); } printf("%d ",MinCostFlow(0,Man+House+1)); } return 0; }
据说可以用KM算法来写,下次补上KM算法的代码。。。