糯米

TI DaVinci, gstreamer, ffmpeg
随笔 - 167, 文章 - 0, 评论 - 47, 引用 - 0
数据加载中……

POJ 2135 Farm Tour 最小费用最大流

第一次写这玩意,还真有点麻烦,出了点问题。然后看了一下别人的代码,
发现双向边,要分成两个单向边来插入。长见识了。
而且费用的值有正有负,最好用SPFA来找最短路径。

思路:
建立一个超级源点,跟点1连起来,容量为2。
建立一个超级汇点,跟点N连起来,容量为2。
其他的边容量均为1。

#include <stdio.h>
#include 
<stdlib.h>
#include 
<string.h>

#define MAX_COST (1 << 30)
#define MAX_E (20032 * 4)
#define MAX_V 2048
#define MAX_CAP 2
#define dbp printf

struct edge_node {
    
int idx, flow, cap, cost;
    
struct edge_node *next;
}
;

struct graph_node {
    
struct edge_node edges[MAX_E], *map[MAX_V], *path_edge[MAX_V];
    
int edges_cnt, vertexs_cnt, path_idx[MAX_V];
    
int min_dis[MAX_V];
}
;

inline 
int min(int a, int b)
{
    
return a < b ? a : b;
}


inline 
void graph_init(struct graph_node *g, int vertexs_cnt)
{
    g
->vertexs_cnt = vertexs_cnt;
    g
->edges_cnt = 0;
    memset(g
->map, 0, vertexs_cnt * sizeof(g->map[0]));
}


inline 
void graph_dump(struct graph_node *g)
{
    
struct edge_node *e;
    
int i;

    
for (i = 0; i < g->vertexs_cnt; i++{
        dbp(
"#%d: ", i);
        
for (e = g->map[i]; e; e = e->next) 
            dbp(
"%dc%d ", e->idx, e->cost);
        dbp(
"\n");
    }

}


inline 
void graph_addedge(struct graph_node *g, 
                          
int from, int to, 
                          
int cost, int cap = 0
                          )
{
    
struct edge_node *e;

    
if (g->edges_cnt >= _countof(g->edges)) {
        printf(
"too many edges\n");
        
return ;
    }


    e 
= &g->edges[g->edges_cnt++];
    e
->idx = to;
    e
->cost = cost;
    e
->cap = cap;
    e
->next = g->map[from];
    g
->map[from] = e;
}


inline 
int __conn_default(struct edge_node *e)
{
    
return 1;
}


inline 
void graph_spfa(struct graph_node *g, int idx, 
                       
int (*conn)(struct edge_node *= __conn_default
                       )
{
    
static int queue[MAX_V], vis[MAX_V], tm, head, tail;
    
int i, val;
    
struct edge_node *e;

    
for (i = 0; i < g->vertexs_cnt; i++)
        g
->min_dis[i] = MAX_COST;
    g
->min_dis[idx] = 0;
    
    head 
= tail = 0;
    tm
++;
    queue[tail
++= idx;

    
while (head != tail) {
        idx 
= queue[head++];
        vis[idx] 
= 0;
        
for (e = g->map[idx]; e; e = e->next) {
            
if (!conn(e))
                
continue;
            val 
= g->min_dis[idx] + e->cost;
            
if (val >= g->min_dis[e->idx])
                
continue;
            g
->path_idx[e->idx] = idx;
            g
->path_edge[e->idx] = e;
            g
->min_dis[e->idx] = val;
            
if (vis[e->idx] == tm) 
                
continue;
            queue[tail
++= e->idx;
            vis[e
->idx] = tm;
        }

    }

}


inline 
int __conn_mfmc(struct edge_node *e)
{
    
return e->cap - e->flow > 0;
}


inline 
void graph_mfmc(struct graph_node *g, int s, int t, int *flow, int *cost)
{
    
int i, j, min_c;
    
struct edge_node *e;

    
for (i = 0; i < g->edges_cnt; i++)
        g
->edges[i].flow = 0;

    
*flow = 0;
    
*cost = 0;
    
while (1{
        graph_spfa(g, s, __conn_mfmc);
        
if (g->min_dis[t] == MAX_COST)
            
break ;
        min_c 
= MAX_CAP;
        
for (i = t; i != s; i = g->path_idx[i]) {
            e 
= g->path_edge[i];
            min_c 
= min(min_c, e->cap - e->flow);
        }

        
for (i = t; i != s; i = g->path_idx[i]) {
            j 
= g->path_edge[i] - g->edges;
            
*cost += g->edges[j].cost * min_c;
            g
->edges[j].flow += min_c;
            g
->edges[j ^ 1].flow -= min_c;
        }

        
*flow += min_c;
    }

}


int main()
{
    
int N, M, from, to, cost, flow;
    
static struct graph_node g;

    freopen(
"e:\\test\\in.txt""r", stdin);

    scanf(
"%d%d"&N, &M);
    graph_init(
&g, N + 2);
    
while (M--{
        scanf(
"%d%d%d"&from, &to, &cost);
        graph_addedge(
&g, from, to, cost, 1);
        graph_addedge(
&g, to, from, -cost, 0);
        graph_addedge(
&g, to, from, cost, 1);
        graph_addedge(
&g, from, to, -cost, 0);
    }

    graph_addedge(
&g, 0102);
    graph_addedge(
&g, 1000);
    graph_addedge(
&g, N, N + 102);
    graph_addedge(
&g, N + 1, N, 00);
    graph_mfmc(
&g, 0, N + 1&flow, &cost);
    printf(
"%d\n", cost);

    
return 0;
}

posted on 2010-04-06 23:40 糯米 阅读(775) 评论(4)  编辑 收藏 引用 所属分类: POJ

评论

# re: POJ 2135 Farm Tour 最小费用最大流  回复  更多评论   

"发现双向边,要分成两个单向边来插入。"
请问一下为什么要建双向边呢?
2010-09-02 00:18 | siurz

# re: POJ 2135 Farm Tour 最小费用最大流  回复  更多评论   

@siurz
同样期待
2011-02-06 16:43 | .。

# re: POJ 2135 Farm Tour 最小费用最大流  回复  更多评论   

@.。
想明白了,因为当a->b的边走了之后,b->a有两条边,其中一条的费用为正,一条的费用为负。显然会选择为负的,而为负的正是刚刚其走过的a->b的反向边,这样就相当于刚刚的a->b没有走。
2011-02-06 16:58 | .。

# re: POJ 2135 Farm Tour 最小费用最大流  回复  更多评论   

如火热
2011-08-17 16:24 |

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理