2015
04-16

# 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.

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，表示选与不选的花费。

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

（注意图中起点和终点的+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;
}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)
{
code[man]=num;
++num;
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])
{
{
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)
else
}
out[t]++,in[s]++;
end=n+2,sta=n+1;
MaxFlow=0;
for(i=1;i<=n;i++)
{
if(out[i]>in[i])
if(out[i]<in[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;
}

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

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

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