首页 > ACM题库 > HDU-杭电 > HDU 4744-Starloop System-网络流-[解题报告]HOJ
2015
09-17

HDU 4744-Starloop System-网络流-[解题报告]HOJ

Starloop System

问题描述 :

At the end of the 200013th year of the Galaxy era, the war between Carbon-based lives and Silicon civilization finally comes to its end with the Civil Union born from the ruins. The shadow fades away, and the new-born Union is opening a new page.

Although the war ended, the affect of the war is far from over. Now the council is busy fixing the transportation system. Before the war, all the stars were connected with artificial wormholes which were destroyed during the war. At the same time, natural wormholes are breaking down with the growing traffic. A new traffic system is on the schedule.

As two civilizations combine, the technology integrates. Scientists find a new traffic system called the Starloop System.

This system is made up of several starloops. People build a starway to connect two stars. A startloop is a closed path with no repetitions of stars or starways allowed, other than the repetition of the starting and ending star. And a starloop contains at least two starts and two starways. A startloop’s cost is the sum of the length of all the starways in it. Length of a starway connecting two stars is floor(x), which x is the euclidean distance between two stars. You can build more than one starway between any two stars, but one starway can only belongs to one starloop.

Sparrow

As the picture above shows, there are two starloops. One is blue and the other one is brown.

As a starloop is set up, each star on the starloop will get a unit of star-energy. So the two blue stars can get one unit of star-energy, and at the same time the black two stars can get two units because they both belong to two starloops. When a star earns a certain number of energy units, the transporter on that star will be activated. One can easily travel between any two stars whose transporter is activated.

Now the council wants to know the minimal cost to build a starloop system on all the stars . In other words, every star’s transporter should be activated

输入:

There are multiple test cases.
For each test case:
There is a line with one integer n which is the number of stars.

The following n lines each describes a star by four integers xi, yi, zi and wi, defined as the spatial coordinate and the number of energy units the star needs to activate the transporter. Please NOTE that getting more than wi energy units will put the star in a dangerous situation, so it is not allowed.
The input ends with n = 0.

1<=n<=100
|xi|,|yi|,|zi|<=200
wi<=50

输出:

There are multiple test cases.
For each test case:
There is a line with one integer n which is the number of stars.

The following n lines each describes a star by four integers xi, yi, zi and wi, defined as the spatial coordinate and the number of energy units the star needs to activate the transporter. Please NOTE that getting more than wi energy units will put the star in a dangerous situation, so it is not allowed.
The input ends with n = 0.

1<=n<=100
|xi|,|yi|,|zi|<=200
wi<=50

样例输入:

3
0 0 2 1
0 2 0 1
2 0 0 1
3
0 0 2 2
0 2 0 1
2 0 0 1
3
0 0 2 3
0 2 0 1
2 0 0 1
0

样例输出:

6
8
-1

·题目

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

·分析

无源汇上下界网络流

每个点拆i和i’两个点,连i->i’上界和下届都为w[i]的边

那么对于a和b,设费用为cost[a][b]

1.连b’->a容量INF,费用cost[a][b]的边

2.连a’->b容量INF,费用cost[a][b]的边

求无源汇最小费用可行流即可

略坑要用zkw

·代码

/**************************************************
 *        Problem:  HDU 4744
 *         Author:  clavichord93
 *          State:  Accepted
 **************************************************/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define sqr(a) ((a) * (a))
using namespace std;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-9;

template <class T>
inline void gmax(T &a, T b) {
    if (a < b) {
        a = b;
    }
}

template <class T>
inline void gmin(T &a, T b) {
    if (a > b) {
        a = b;
    }
}

const int MAX_N = 105;
const int MAX_E = 50005;

struct Edge {
    int dest;
    int capa;
    int cost;
    Edge *next;
    Edge *pair;
    Edge() {}
    Edge(int _dest, int _capa, int _cost, Edge *_next) : dest(_dest), capa(_capa), cost(_cost), next(_next) {}
};

Edge EdgePool[MAX_E];
Edge *EP;
Edge *e[2 * MAX_N];
int s;
int t;
int maxflow;
int mincost;
int dist[2 * MAX_N];
bool vis[2 * MAX_N];

int n;
int x[MAX_N];
int y[MAX_N];
int z[MAX_N];
int w[MAX_N];
int cost[MAX_N][MAX_N];

inline void addedge(int a, int b, int c, int d) {
    e[a] = new(EP++)Edge(b, c, d, e[a]);
    e[b] = new(EP++)Edge(a, 0, -d, e[b]);
    e[a]->pair = e[b];
    e[b]->pair = e[a];
}

int aug(int i, int delta) {
	if (i == t) {
        maxflow += delta;
		mincost += delta * dist[s];
		return delta;
	}
	vis[i] = true;
	for (Edge *j = e[i]; j; j = j->next) {
        if (!vis[j->dest] && j->capa && dist[j->dest] + j->cost == dist[i]) {
            int flow = aug(j->dest, min(j->capa, delta));
            if (flow) {
                j->capa -= flow;
                j->pair->capa += flow;
                return flow;
            }
        }
    }
	return 0;
}

bool modlabel() {
	int delta = INF;
	for (int i = s; i <= t; i++) {
        if (vis[i]) {
            for(Edge *j=e[i]; j; j = j->next) {
                if(j->capa && !vis[j->dest]) {
                    gmin(delta,dist[j->dest] + j->cost - dist[i]);
                }
            }
        }
	}
	if (delta == INF) {
        return false;
    }
	for (int i = s; i <= t; i++) {
        if (vis[i]) {
            dist[i] += delta;
            vis[i] = false;
        }
	}
	return true;
}

void costflow() {
    maxflow = 0;
    mincost = 0;
	do {
		do {
            memset(vis, 0, sizeof(vis));
		} while (aug(s, INF));
	} while (modlabel());
}

int main() {
    #ifdef LOCAL_JUDGE
    freopen("in.txt", "r", stdin);
    #endif
    while (scanf("%d", &n), n) {
        EP = EdgePool;
        memset(e, 0, sizeof(e));
        memset(dist, 0, sizeof(dist));

        int sumW = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d %d %d %d", &x[i], &y[i], &z[i], &w[i]);
            sumW += w[i];
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                double dist = sqrt(sqr(x[i] - x[j]) + sqr(y[i] - y[j]) + sqr(z[i] - z[j]));
                cost[i][j] = (int)(floor(dist) + 0.5);
            }
        }

        s = 0;
        t = n * 2 + 1;
        for (int i = 1; i <= n; i++) {
            addedge(s, 2 * i, w[i], 0);
            //addedge(2 * i - 1, 2 * i, INF, 0);
            for (int j = 1; j <= n; j++) {
                if (i != j) {
                    addedge(2 * i, 2 * j - 1, INF, cost[i][j]);
                }
            }
            addedge(2 * i - 1, t, w[i], 0);
        }

        costflow();

        if (maxflow == sumW) {
            printf("%d\n", mincost);
        }
        else {
            printf("-1\n");
        }
    }

    return 0;
}

参考:http://blog.csdn.net/alpc_neverfarewell/article/details/39066157