首页 > ACM题库 > HDU-杭电 > HDU 4067-Random Maze-最短路径-[解题报告]HOJ
2015
04-16

HDU 4067-Random Maze-最短路径-[解题报告]HOJ

Random Maze

问题描述 :

In the game “A Chinese Ghost Story”, there are many random mazes which have some characteristic:
1.There is only one entrance and one exit.
2.All the road in the maze are unidirectional.
3.For the entrance, its out-degree = its in-degree + 1.
4.For the exit, its in-degree = its out-degree + 1.
5.For other node except entrance and exit, its out-degree = its in-degree.
Random Sequence

There is an directed graph, your task is removing some edge so that it becomes a random maze. For every edge in the graph, there are two values a and b, if you remove the edge, you should cost b, otherwise cost a.
Now, give you the information of the graph, your task if tell me the minimum cost should pay to make it becomes a random maze.

输入:

The first line of the input file is a single integer T.
The rest of the test file contains T blocks.
For each test case, there is a line with four integers, n, m, s and t, means that there are n nodes and m edges, s is the entrance’s index, and t is the exit’s index. Then m lines follow, each line consists of four integers, u, v, a and b, means that there is an edge from u to v.
2<=n<=100, 1<=m<=2000, 1<=s, t<=n, s != t. 1<=u, v<=n. 1<=a, b<=100000

输出:

The first line of the input file is a single integer T.
The rest of the test file contains T blocks.
For each test case, there is a line with four integers, n, m, s and t, means that there are n nodes and m edges, s is the entrance’s index, and t is the exit’s index. Then m lines follow, each line consists of four integers, u, v, a and b, means that there is an edge from u to v.
2<=n<=100, 1<=m<=2000, 1<=s, t<=n, s != t. 1<=u, v<=n. 1<=a, b<=100000

样例输入:

2
2 1 1 2
2 1 2 3
5 6 1 4
1 2 3 1
2 5 4 5
5 3 2 3
3 2 6 7
2 4 7 6
3 4 10 5

样例输出:

Case 1: impossible
Case 2: 27

/*

  // 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4067

    解题报告人:SpringWater
    题意描述:

200个点的图,告诉你一些单向边,每条边两个值a和b,表示选与不选的花费。

现在让起点的出度-入度=1,终点的入度-出度=1,其他点的入度=出度。

问是否可能,可能的话最小花费是多少。

具体算法如下:

Sum表示初始图的代价,开始时为0.

对于b>=a的边,那么默认这条边连接,边权为b-a(删除的费用),当前费用sum+=a,由于默认这条边连接,那么出度[from]++, 入度[to]++

对于b<a的边,那么默认这条边没有连接,加入to到from的反向边,在流中就表示用这条反向边维护节点度的平衡,边权为a-b(添加的费用),当前费用sum+=b,由于默认不加这条边,所以出度入度就不用更新。

超级源点S,汇点T

出度>入度的,S连接之,容量为差值

入度>出度的,连接T,容量为差值

(注意图中起点和终点的+1-1的要求)

这样,如果满流,每个节点就满足了度的要求。

Sum+费用就是答案。

 

  回头感悟:这题时我acm以来用时最多的一个题目,感觉有些悲剧,不过终于把他拿下来了,还是蛮兴奋的,因为在为了ac它的过程中,

  我同时学到了其他很多有关网络流的算法知识,如最小最大网络流求法,有上下界的最小最大网络,最小费用最大流;特别是让人拍案叫绝的

  加边法,和让我感叹不已的spfa算法;还有就是发现了Djstla的一个经典局限性,(即对于存在负权边不适用)!不过此题最经典的地方还是
 
  在数学建模上:将此问题转化为一个求最大流;是我觉得最巧妙的地方,原因是:即使求最小费用最大流虽然已经涉及到了很多经典算法,但
 
  是这些方法都已经是 模板了,不足为绝唱(不过就我亲自实现了一番的感觉而言,还是感觉它足以让人累疼,加肉疼!)

 
*/

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define MAXEDGE 54000
#define BREAK 1000000000
struct Edge{
    int flow;
    int cost;
    int point;
    int forhead;
}edge[MAXEDGE];
int path[210];
int que[220];
int code[210],num;
int weight[210];
int visit[210];
int in[210],out[210];
int AddEdge(int man,int son,int cost,int flow)
{
    edge[num].cost=cost,edge[num].flow=flow,edge[num].forhead=code[man],edge[num].point=son;
    code[man]=num;
    ++num;
    edge[num].cost=-cost,edge[num].flow=0,edge[num].forhead=code[son],edge[num].point=man;
    code[son]=num;
    ++num;
    return 0;
}
int FindAMinCostWay(int n,int sta,int end)
{
    int i,j;
    int l,r,temp;
    for(i=1;i<=n;i++)
        weight[i]=BREAK;
    l=0,r=1;
    que[0]=sta;
    weight[sta]=0;
    for(i=que[l];l!=r;i=que[l])
    {
        for(j=code[i],visit[i]=0;j!=-1;j=edge[j].forhead)
        {
            if(edge[j].flow&&(weight[edge[j].point]>(temp=weight[i]+edge[j].cost)))
            {
                weight[edge[j].point]=temp;
                path[edge[j].point]=j^1;
                if(visit[edge[j].point])continue;
                que[r]=edge[j].point;
                visit[edge[j].point]=1;
                ++r;
                if(r>=200)
                    r=0;
            }
        }
        ++l;
        if(l>=200)
            l=0;
    }
    if(weight[end]==BREAK)
        return 0;
    else
        return 1;///这里把我坑害惨了;因为weight[end]==0时也可能满足
}                ///,使得返回值即使是0不能排除存在一条最短路径
int main()
{
    int T,cas;
    int n,m,s,t;
    int u,v,a,b;
    int end,sta;
    int MaxFlow;
    int i;
    int ans,flow,cost;
    freopen("input.txt","r",stdin);
    scanf("%d",&T);
    for(cas=1;cas<=T;cas++)
    {
        scanf("%d%d%d%d",&n,&m,&s,&t);
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        num=0;
        memset(code,-1,sizeof(code));
        ans=0;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d%d",&u,&v,&a,&b);
            ans+=(a<b)?a:b;
            if(a<b)
                AddEdge(v,u,b-a,1),out[u]++,in[v]++;
            else
                AddEdge(u,v,a-b,1);
        }
        out[t]++,in[s]++;
        end=n+2,sta=n+1;
        MaxFlow=0;
        for(i=1;i<=n;i++)
        {
            if(out[i]>in[i])
                AddEdge(i,end,0,out[i]-in[i]),MaxFlow+=out[i]-in[i];
            if(out[i]<in[i])
                AddEdge(sta,i,0,in[i]-out[i]);
        }
        flow=0;
        while(1)
        {
            cost=FindAMinCostWay(n+2,sta,end);
            if(cost)
            {
                ++flow;
                ans+=weight[end];
                path[sta]=-1;
            for(i=end;path[i]!=-1;i=edge[path[i]].point)
                    edge[path[i]].flow+=1,edge[path[i]^1].flow-=1;
            }
            else
                break;
        }
        printf("Case %d: ",cas);
        if(MaxFlow==flow)
            printf("%d\n",ans);
        else
            printf("impossible\n");
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/sprintfwater/article/details/7861860


  1. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  3. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。

  4. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  5. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。