首页 > 搜索 > BFS搜索 > HDU 4309-Seikimatsu Occult Tonneru-网络流-[解题报告]HOJ
2015
05-23

HDU 4309-Seikimatsu Occult Tonneru-网络流-[解题报告]HOJ

Seikimatsu Occult Tonneru

问题描述 :

During the world war, to avoid the upcoming Carpet-bombing from The Third Reich, people in Heaven Empire went to Great Tunnels for sheltering.
There are N cities in Heaven Empire, where people live, with 3 kinds of directed edges connected with each other. The 1st kind of edges is one of Great Tunnels( no more than 20 tunnels) where a certain number of people can hide here; people can also go through one tunnel from one city to another. The 2nd kind of edges is the so-called Modern Road, which can only let people go through. The 3rd kind of edges is called Ancient Bridge and all the edges of this kind have different names from others, each of which is named with one of the twelve constellations( such as Libra, Leo and so on); as they were build so long time ago, they can be easily damaged by one person’s pass. Well, for each bridge, you can spend a certain deal of money to fix it. Once repaired, the 3rd kind of edges can let people pass without any limitation, namely, you can use one bridge to transport countless people. As for the former two kinds of edges, people can initially go through them without any limitation.
We want to shelter the most people with the least money.
Now please tell me the largest number of people who can hide in the Tunnels and the least money we need to spend to realize our objective.

输入:

Multiple Cases.
The first line, two integers: N (N<=100), m (m<=1000). They stands for the number of cities and edges.
The next line, N integers, which represent the number of people in the N cities.
Then m lines, four intergers each: u, v, w, p (1<=u, v<=N, 0<=w<=50). A directed edge u to v, with p indicating the type of the edge: if it is a Tunnel then p < 0 and w means the maximum number people who can hide in the the tunnel; if p == 0 then it is a Modern Road with w means nothing; otherwise it is an Ancient Bridge with w representing the cost of fixing the bridge. We promise there are no more than one edge from u to v.

输出:

Multiple Cases.
The first line, two integers: N (N<=100), m (m<=1000). They stands for the number of cities and edges.
The next line, N integers, which represent the number of people in the N cities.
Then m lines, four intergers each: u, v, w, p (1<=u, v<=N, 0<=w<=50). A directed edge u to v, with p indicating the type of the edge: if it is a Tunnel then p < 0 and w means the maximum number people who can hide in the the tunnel; if p == 0 then it is a Modern Road with w means nothing; otherwise it is an Ancient Bridge with w representing the cost of fixing the bridge. We promise there are no more than one edge from u to v.

样例输入:

4 4
2 1 1 0
1 2 0 0
1 3 0 0
2 4 1 -1
3 4 3 -1

4 4
2 1 1 0
1 2 0 0
1 3 3 1
2 4 1 -1
3 4 3 -1

样例输出:

4 0
4 3

http://acm.hdu.edu.cn/showproblem.php?pid=4309

题意: n个点,每个点有初始的值 ,三种 通道,1、隧道:可以用来躲避,有固定的容量,也可以用来传递。2、普通的道路,可以无限的通过。3、桥(最多有12座):不花费的话能通过一人,修之后可以无限通过。问最少花费最大可以隐藏人数。

解:

     网络流 + 枚举

官方题解:

先不考虑可以修复的桥的性质,则可以将模型简化为n个点的人通过有通过人数上限的有向边,到达一些有人数上限的特殊的边(隧道)。
可以建立最大流模型来求解,增加一个源点S,和一个汇点T。S向每个有人的点,连一条容量为人数的边,图中普通的u->v的有向边,连一条u->v的流量为无穷的边,桥的流量则为1。对于隧道,每个隧道可以虚拟出一个点,如u->v的隧道,可以虚拟一个点x,连接u->x,x->v的流量无穷的边,和x->T的流量为隧道人数上限的边,求解最大流即可得到最大人数。
现在考虑桥的问题,题目中说明了桥最多只有12座,故可以2^12枚举修复哪些桥,不修复的桥没有花费,连接的边流量为1,要修复的桥则计算花费,边的流量为无穷,这样进行2^12次最大流就可以得到最优解。

#include <cstdio>
#include <cstring>
const int MAXN = 205;
const int MAXM = 2505;
const int INF = 1000000000;

struct Edge
{
    int u, v, next, flow;
}edge[MAXM], redge[MAXM];
int edgeNumber, head[MAXN], rhead[MAXN];
int source = MAXN - 1;
int destination = MAXN - 2;
int depth[MAXN];

inline int min(int x, int y)
{
    return x < y ? x : y;
}

void addEdgeSub(int u, int v, int flow)
{
    edge[edgeNumber].u = u;
    edge[edgeNumber].v = v;
    edge[edgeNumber].flow = flow;
    edge[edgeNumber].next = head[u];
    head[u] = edgeNumber ++;
}

void addEdge(int u, int v, int flow)
{
    addEdgeSub(u, v, flow);
    addEdgeSub(v, u, 0);
}

int n, m;
int bridgePosition[MAXN];
int bridgeCost[MAXN];
int bridgeNumber;

bool bfs(int start, int end)
{
    int front = 0, rear = 0;
    int queue[MAXN];
    memset(depth, -1, sizeof(depth));
    queue[front++] = start;
    depth[start] = 0;
    while(rear < front)
    {
        int k = queue[rear++];
        for(int i=head[k];i!=-1;i=edge[i].next)
        {
            int to = edge[i].v;
            if(-1 == depth[to] && edge[i].flow > 0)
            {
                depth[to] = depth[k] + 1;
                queue[front++] = to;
            }
        }
    }
    return -1 != depth[end];
}

int dinic(int start, int end, int sum)
{
    if(start == end)
    {
        return sum;
    }
    int temp = sum;
    for(int i=head[start];i!=-1 && sum;i=edge[i].next)
    {
        if(edge[i].flow > 0 && depth[edge[i].v] == depth[start] + 1)
        {
            int a = dinic(edge[i].v, end, min(sum, edge[i].flow));
            edge[i].flow -= a;
            edge[i^1].flow += a;
            sum -= a;
        }
    }
    return temp - sum;
}

int maxFlow(int start, int end)
{
    int result = 0;
    while(bfs(start, end))
    {
        result += dinic(start, end, INF);
    }
    return result;
}

int main()
{
    int u, v, w, p;
    while(~scanf("%d%d", &n, &m))
    {
        int pointNumber = n + 1;
        edgeNumber = 0;
        bridgeNumber = 0;
        memset(head, -1, sizeof(head));
        for(int i=1;i<=n;++i)
        {
            scanf("%d", &w);
            addEdge(source, i, w);
        }
        for(int i=0;i<m;++i)
        {
            scanf("%d%d%d%d",&u,&v,&w,&p);
            if(p < 0)
            {
                addEdge(u, pointNumber, INF);
                addEdge(pointNumber, v, INF);
                addEdge(pointNumber, destination, w);
                ++ pointNumber;
            }
            else if(p == 0)
            {
                addEdge(u, v, INF);
            }
            else
            {
                bridgePosition[bridgeNumber] = edgeNumber;
                bridgeCost[bridgeNumber] = w;
                addEdge(u, v, 1);
                ++ bridgeNumber;
            }
        }
        memcpy(redge, edge, sizeof(redge));
        memcpy(rhead, head, sizeof(rhead));
        int minCost = INF, maxPeople = - INF;
        for(int i=0;i<(1<<bridgeNumber);++i)
        {
            memcpy(edge, redge, sizeof(edge));
            memcpy(head, rhead, sizeof(head));
            int cost = 0;
            for(int j=0;j<bridgeNumber;++j)
            {
                if(i&(1 << j))
                {
                    cost += bridgeCost[j];
                    edge[bridgePosition[j]].flow = INF;
                }
            }
            int people = maxFlow(source, destination);
            if(people > maxPeople)
            {
                maxPeople = people;
                minCost = cost;
            }
            else if(people == maxPeople)
            {
                minCost = min(minCost, cost);
            }
        }
        if(maxPeople > 0)
        {
            printf("%d %d\n", maxPeople, minCost);
        }
        else
        {
            printf("Poor Heaven Empire\n");
        }
    }
    return 0;
}

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

参考:http://blog.csdn.net/julyana_lin/article/details/8070949