首页 > ACM题库 > HDU-杭电 > hdu 2448 Mining Station on the Sea-二分图-[解题报告]C++
2014
01-26

hdu 2448 Mining Station on the Sea-二分图-[解题报告]C++

Mining Station on the Sea

问题描述 :

The ocean is a treasure house of resources and the development of human society comes to depend more and more on it. In order to develop and utilize marine resources, it is necessary to build mining stations on the sea. However, due to seabed mineral resources, the radio signal in the sea is often so weak that not all the mining stations can carry out direct communication. However communication is indispensable, every two mining stations must be able to communicate with each other (either directly or through other one or more mining stations). To meet the need of transporting the exploited resources up to the land to get put into use, there build n ports correspondently along the coast and every port can communicate with one or more mining stations directly.

Due to the fact that some mining stations can not communicate with each other directly, for the safety of the navigation for ships, ships are only allowed to sail between mining stations which can communicate with each other directly.

The mining is arduous and people do this job need proper rest (that is, to allow the ship to return to the port). But what a coincidence! This time, n vessels for mining take their turns to take a rest at the same time. They are scattered in different stations and now they have to go back to the port, in addition, a port can only accommodate one vessel. Now all the vessels will start to return, how to choose their navigation routes to make the total sum of their sailing routes minimal.

Notice that once the ship entered the port, it will not come out!

输入:

There are several test cases. Every test case begins with four integers in one line, n (1 = <n <= 100), m (n <= m <= 200), k and p. n indicates n vessels and n ports, m indicates m mining stations, k indicates k edges, each edge corresponding to the link between a mining station and another one, p indicates p edges, each edge indicating the link between a port and a mining station. The following line is n integers, each one indicating one station that one vessel belongs to. Then there follows k lines, each line including 3 integers a, b and c, indicating the fact that there exists direct communication between mining stations a and b and the distance between them is c. Finally, there follows another p lines, each line including 3 integers d, e and f, indicating the fact that there exists direct communication between port d and mining station e and the distance between them is f. In addition, mining stations are represented by numbers from 1 to m, and ports 1 to n. Input is terminated by end of file.

输出:

There are several test cases. Every test case begins with four integers in one line, n (1 = <n <= 100), m (n <= m <= 200), k and p. n indicates n vessels and n ports, m indicates m mining stations, k indicates k edges, each edge corresponding to the link between a mining station and another one, p indicates p edges, each edge indicating the link between a port and a mining station. The following line is n integers, each one indicating one station that one vessel belongs to. Then there follows k lines, each line including 3 integers a, b and c, indicating the fact that there exists direct communication between mining stations a and b and the distance between them is c. Finally, there follows another p lines, each line including 3 integers d, e and f, indicating the fact that there exists direct communication between port d and mining station e and the distance between them is f. In addition, mining stations are represented by numbers from 1 to m, and ports 1 to n. Input is terminated by end of file.

样例输入:

3 5 5 6
1 2 4
1 3 3
1 4 4
1 5 5
2 5 3
2 4 3
1 1 5
1 5 3
2 5 3
2 4 6
3 1 4
3 2 2

样例输出:

13

最小费用最大流。

多源多汇点,把源点S 到 每个船所在的station建一条容量为1,cost为0的单向边。

把每个port到 汇点T 建一条容量为1,cost为1的但单向边。

注意station之间的边的容量要建为inf。。

而且port 和 station之间是单向边。开始建的双向,WA死了,搜题解全是最短路+KM = = 害的我都怀疑我的想法了。

题目这句话 Notice that once the ship entered the port, it will not come out!

说明,船不能经过一个port 到达另外一个port。。。

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define BUG puts("here!!!")

using namespace std;

const int MAX = 310;
const int LALA = 200000;
struct NODE{  
    int from,to,cap,cost;  
    int next;  
};  
NODE node[LALA];  			// 根据题意 
int p[MAX];  				// 相当于指针数组 
int cou,n,m;  
void init()  
{  
    memset(p,-1,sizeof(p));    
    cou = 2;    			// 初始化为偶数 
}  
void Add(int u,int v,int cap,int cost)  
{  
    node[cou].from = u;  
    node[cou].to = v;  
    node[cou].cap = cap;  
    node[cou].cost = cost;  
    node[cou].next = p[u];  
    p[u] = cou++;  
      
    node[cou].from = v;  
    node[cou].to = u;  
    node[cou].cap = 0;  
    node[cou].cost = -cost;  
    node[cou].next = p[v];  
    p[v] = cou++;  
}  
int MincostMaxflow(int s,int t,int n )  
{  
    queue<int> q;  
    int inq[MAX],pre[MAX],dis[MAX],re[MAX];  
    int u,v,i,a,c = 0,ind,cost,cap;  
    while(1)  
    {  
        memset(inq,0,sizeof(inq));  
        fill(dis,dis+MAX,INT_MAX);
        dis[s] = 0;  
        inq[s] = 1;  
        pre[s] = s;  
        q.push(s);  
        while( !q.empty() )  
        {  
            u = q.front();  
            q.pop();  
            inq[u] = 0;  
            ind = p[u];  
            while( ind != -1 )  
            {  
                u = node[ind].from;  
                v = node[ind].to;  
                cost = node[ind].cost;  
                cap = node[ind].cap;  
                if( cap > 0 && dis[v] > dis[u] + cost )  
                {  
                    dis[v] = dis[u] + cost;  
                    pre[v] = u;  
                    re[v] = ind;  
                    if( !inq[v] )  
                    {  
                        q.push(v);  
                        inq[v] = 1;  
                    }  
                }  
                ind = node[ind].next;     
            }  
        }  
        if( dis[t] == INT_MAX ) break; 
        a = INT_MAX;  
        for(u=t; u!=s; u=pre[u])  
            if( node[re[u]].cap < a )    
                a = node[re[u]].cap;  
        for(u=t; u!=s; u=pre[u])  
        {  
            node[re[u]^1].cap += a;   
            node[re[u]].cap -= a;  
        }  
        c += dis[t]*a;  
    }  
    return c;  
}  

int main()
{
	int n, m, k, pp, from, to, len;
	int S, T;
	
	while( ~scanf("%d%d%d%d", &n, &m, &k, &pp) )
	{
		S = 0;
		T = n + m + 1;
		init();
		for(int i=0; i<n; i++)
		{
			scanf("%d", &to);
			Add(S, to, 1, 0);
		}
		
		while( k-- )
		{
			scanf("%d%d%d", &from, &to, &len);
			Add(from, to, m, len);
			Add(to, from, m, len);
		}
		
		while( pp-- )
		{
			scanf("%d%d%d", &from, &to, &len);
			Add(to, from + m, 1, len);
		}
		
		for(int i=1; i<=n; i++)
			Add(i + m, T, 1, 0);

		int ans = MincostMaxflow(S, T, n + m + 2);
		printf("%d\n", ans);
	}

return 0;
}

解题转自:http://blog.csdn.net/zxy_snow/article/details/6716802


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  3. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了