POJ 2195 地图的最小费用最大流 - c++编程基础

TOP

POJ 2195 地图的最小费用最大流

2015-07-20 17:49:37 来源: 作者: 【大中小】浏览:1次

思路：这题刚开始看就知道是最小费用最大流了，因为求出最优嘛，而且要m,H要一一对应，所以不是二分图匹配就是最小费用最大流。

不过，刚开始还在想每个m与H之间的最小花费如何求，难道要用dfs搜索吗？这样想之后看了下题目给的时间是1000ms，然后就把dfs搜索m与H之间的最短距离排除了。然后想了想，其实尼玛太简单了，因为题目说了只能垂直与竖直的走，所以最短距离不就是两个横坐标相减与两个纵坐标相减之和嘛！

然后每对m与H之间都连边，流量为1（因为每对匹配不能重复），费用为它们之间的距离即花费；然后建超级源点和超级汇点，源点和每个m相连，流量和上面一样也是1（单一匹配嘛），费用为0，因为它们之间不产生花费；汇点和源点建边一样。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include
  
   
#include
   
     #include
    
      #include
     
       #include
       #include
       
         #include
        
          #include
         
           #include
          
            #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
           
            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


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：POJ 3368 Frequent values（线段..	下一篇：CodeForces 34D Road Map

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: