注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

1001: [BeiJing2006]狼抓兔子  

2011-10-05 22:39:03|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Description
现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到,但抓兔子还是比较在行的,而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下面这样一个网格的地形:左上角点为(1,1),右下角点为(N,M)(上图中N=4,M=5).有以下三种类型的道路 1:(x,y)<==>(x+1,y) 2:(x,y)<==>(x,y+1) 3:(x,y)<==>(x+1,y+1) 道路上的权值表示这条路上最多能够通过的兔子数,道路是无向的. 左上角和右下角为兔子的两个窝,开始时所有的兔子都聚集在左上角(1,1)的窝里,现在它们要跑到右下解(N,M)的窝中去,狼王开始伏击这些兔子.当然为了保险起见,如果一条道路上最多通过的兔子数为K,狼王需要安排同样数量的K只狼,才能完全封锁这条道路,你需要帮助狼王安排一个伏击方案,使得在将兔子一网打尽的前提下,参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦.

1001: [BeiJing2006]狼抓兔子 - vfleaking - vfleaking的博客

Input

第一行为N,M.表示网格的大小,N,M均小于等于1000.接下来分三部分 第一部分共N行,每行M-1个数,表示横向道路的权值. 第二部分共N-1行,每行M个数,表示纵向道路的权值. 第三部分共N-1行,每行M-1个数,表示斜向道路的权值. 输入文件保证不超过10M

Output

输出一个整数,表示参与伏击的狼的最小数量.

Sample Input

3 4
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6

Sample Output

14

事实上,这道题在问:在这个图中取哪些边使边的长度之和最小,而且去掉这些边START不能走到END?可以想到,把原图的边看成点,把原图的点看成边,然后从右上角到左下角求一次最短路即可。
简单点说:构造对偶图求原图最小割。

代码:(小心观看)
#include <iostream>
#include <cstdio>
#include <list>
#include <vector>
using namespace std;

const int MaxN = 1000, MaxM = 1000;
const int INF = 2147483647;

struct vertex
{
    short x, y;
    bool type;
    
    vertex()
    {
    }
    
    vertex(int mx, int my, int mtype)
    {
        x = mx;
        y = my;
        type = mtype;
    }
};

struct edge
{
    vertex u;
    int l;
    
    edge(vertex mu, int ml)
    {
        u = mu;
        l = ml;
    }
};

vector<edge> map[MaxN + 2][MaxM + 2][2];
int dist[MaxN + 2][MaxM + 2][2];
bool book[MaxN + 2][MaxM + 2][2];
int n, m;
list<vertex> q;

int SPFA()
{
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            dist[i][j][0] = INF;
            dist[i][j][1] = INF;
            book[i][j][0] = false;
            book[i][j][1] = false;
        }
    }
    
    q.push_back(vertex(0, m, 0));
    dist[0][m][0] = 0;
    book[0][m][0] = true;
    
    while (!q.empty())
    {
        vertex v = *q.begin();
        q.erase(q.begin());
        book[v.x][v.y][v.type] = false;
        
        vector<edge> *l = &map[v.x][v.y][v.type];
        
        for (vector<edge>::iterator i = l->begin(); i != l->end(); i++)
        {
            vertex u = i->u;
            int l = i->l;
            if (dist[v.x][v.y][v.type] + l < dist[u.x][u.y][u.type])
            {
                dist[u.x][u.y][u.type] = dist[v.x][v.y][v.type] + l;
                if (!book[u.x][u.y][u.type] && !(u.x == n && u.y == 0 && u.type == 0))
                {
                    vertex b = *q.begin();
                    if (dist[b.x][b.y][b.type] > dist[u.x][u.y][u.type])
                        q.push_front(u);
                    else
                        q.push_back(u);
                    book[u.x][u.y][u.type] = true;
                }
            }
        }
    }
    return dist[n][0][0];
}

int main()
{
    //freopen("1001.in", "r", stdin);
    //freopen("1001.out", "w", stdout);

    cin >> n >> m;
    if (n == 1 && m == 1)
    {
        cout << 0 << endl;
        return 0;
    }
    
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            map[i][j][0].reserve(4);
            map[i][j][1].reserve(4);
        }
    }
    
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < m; j++)
        {
            int l;
            scanf("%d", &l);
            map[i - 1][j][1].push_back(edge(vertex(i, j, 0), l));
            map[i][j][0].push_back(edge(vertex(i - 1, j, 1), l));
        }
    }
    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            int l;
            scanf("%d", &l);
            map[i][j - 1][0].push_back(edge(vertex(i, j, 1), l));
            map[i][j][1].push_back(edge(vertex(i, j - 1, 0), l));
        }
    }
    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j < m; j++)
        {
            int l;
            scanf("%d", &l);
            map[i][j][0].push_back(edge(vertex(i, j, 1), l));
            map[i][j][1].push_back(edge(vertex(i, j, 0), l));
        }
    }
    for (int i = 0; i < m; i++)
    {
        map[0][i][1].push_back(edge(vertex(0, i + 1, 1), 0));
        map[0][i + 1][1].push_back(edge(vertex(0, i, 1), 0));
        map[n][i][0].push_back(edge(vertex(n, i + 1, 0), 0));
        map[n][i + 1][0].push_back(edge(vertex(n, i, 0), 0));
    }
    for (int i = 0; i < n; i++)
    {
        map[i][0][0].push_back(edge(vertex(i + 1, 0, 0), 0));
        map[i + 1][0][0].push_back(edge(vertex(i, 0, 0), 0));
        map[i][m][1].push_back(edge(vertex(i + 1, m, 1), 0));
        map[i + 1][m][1].push_back(edge(vertex(i, m, 1), 0));
    }
    map[0][m][0].push_back(edge(vertex(0, m, 1), 0));
    map[0][m][1].push_back(edge(vertex(0, m, 0), 0));
    map[n][0][0].push_back(edge(vertex(n, 0, 1), 0));
    map[n][0][1].push_back(edge(vertex(n, 0, 0), 0));
    
    cout << SPFA() << endl;
    
    return 0;
}
 
  评论这张
 
阅读(1382)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017