Random Maze
Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 908 Accepted Submission(s): 298
Problem Description
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.
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.
Input
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 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
Output
For each case, if it is impossible to work out the random maze, just output the word “impossible”, otherwise output the minimum cost.(as shown in the sample output)
Sample Input
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
Sample Output
Case 1: impossible Case 2: 27
Source
Recommend
lcy
转某大牛思路：
重新为每个边建立权值！
1.如果有边（u,v,a,b) 并且a<=b，那么建立边（v,u,1，b-a) sum+=a,如果要恢复此边需花费 b-a 的费用；in[u]++,out[v]++;
2.如果有边（u,v,a,b) 并且a>b，那么建立边（u,v,1，a-b) sum+=b,如果要删除此边需花费 a-b 的费用；
3.另需t和s 建立一条虚边，in[s]++,out[t]++;
4最后建立一个超级源点S 和超级汇点T,则如果对于点 i in[i]>out[i] 那么建立边（S,i,in[i]-out[i]，0);
相反 建立边（i,T,out[i]-in[i]，0);
最小费用最大流后，如果max_flow=到汇点t所有容量只和
答案即为：sum+max_flow;
1.如果有边（u,v,a,b) 并且a<=b，那么建立边（v,u,1，b-a) sum+=a,如果要恢复此边需花费 b-a 的费用；in[u]++,out[v]++;
2.如果有边（u,v,a,b) 并且a>b，那么建立边（u,v,1，a-b) sum+=b,如果要删除此边需花费 a-b 的费用；
3.另需t和s 建立一条虚边，in[s]++,out[t]++;
4最后建立一个超级源点S 和超级汇点T,则如果对于点 i in[i]>out[i] 那么建立边（S,i,in[i]-out[i]，0);
相反 建立边（i,T,out[i]-in[i]，0);
最小费用最大流后，如果max_flow=到汇点t所有容量只和
答案即为：sum+max_flow;
第四步的意义是如果该点的入度不等于出度，则加入in[i]-out[i](或out[i]-in[i]) 的流量使其走1,2部加入的反向边 使其入度==出度
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
struct node
{
int u,v,f,c;
};
node e[50000];
const int inf= 99999999;
int d[250],first[250],next[50000],p[250],preedge[250],cc;
int in[250],out[250];
int ans_flow,ans_cost;
inline void add_edge(int u,int v,int f,int c)
{
e[cc].u=u;
e[cc].v=v;
e[cc].f=f;
e[cc].c=c;
next[cc]=first[u];
first[u]=cc;
cc++;
e[cc].u=v;
e[cc].v=u;
e[cc].f=0;
e[cc].c=-c;
next[cc]=first[v];
first[v]=cc;
cc++;
}
bool spfa(int s,int t)
{
int inq[250];
memset(inq,0,sizeof(inq));
memset(p,-1,sizeof(p));
memset(preedge,-1,sizeof(preedge));
int i;
for(i=0;i<=t;i++)
d[i]=inf;
d[s]=0;
queue<int> q;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
inq[u]=0;
for(i=first[u];i!=-1;i=next[i])
{
if(e[i].f)
{
int v=e[i].v;
if(d[v]>d[u]+e[i].c)
{
p[v]=u;
preedge[v]=i;
d[v]=d[u]+e[i].c;
if(!inq[v])
{
inq[v]=1;
q.push(v);
}
}
}
}
}
if(d[t]>=inf)
return false;
else
return true;
}
void min_cost_flow(int s,int t)
{
ans_flow=0;
ans_cost=0;
while(spfa(s,t))
{
int u=t;
int mm=inf;
while(p[u]!=-1)
{
mm=min(mm,e[preedge[u]].f);
u=p[u];
}
u=t;
while(p[u]!=-1)
{
e[preedge[u]].f-=mm;
e[preedge[u]^1].f+=mm;
u=p[u];
}
ans_flow+=mm;
ans_cost+=mm*d[t];
}
}
int main()
{
int tt;
scanf("%d",&tt);
int cas;
for(cas=1;cas<=tt;cas++)
{
memset(first,-1,sizeof(first));
memset(next,-1,sizeof(next));
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
cc=0;
int n,m,s,t;
int sum=0;
scanf("%d%d%d%d",&n,&m,&s,&t);
int i;
for(i=0;i<m;i++)
{
int u,v,a,b;
scanf("%d%d%d%d",&u,&v,&a,&b);
if(a<b)
{
in[v]++,out[u]++;
add_edge(v,u,1,b-a);
sum+=a;
}
else
{
add_edge(u,v,1,a-b);
sum+=b;
}
}
in[s]++;
out[t]++;
int S=0;
int T=n+1;
int ss=0;
for(i=1;i<=n;i++)
{
if(in[i]>out[i])
{
add_edge(S,i,in[i]-out[i],0);
ss=ss+in[i]-out[i];
}
else if(in[i]<out[i])
{
add_edge(i,T,out[i]-in[i],0);
}
}
min_cost_flow(S,T);
printf("Case %d: ",cas);
if(ans_flow==ss)
printf("%d\n",sum+ans_cost);
else
printf("impossible\n");
}
return 0;
}