實機體驗,再天天抽M8老王現身說法關鍵字魅力!攝影界美人正妹指定相機款台灣設計引領全球 雙鏡...
2013-05-19 21:36:10 人氣(23) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][DLX、最少重覆覆蓋] 10160 - Servicing Stations

0
收藏
0
推薦

Problem D: Servicing stations


A company offers personal computers for sale in N towns (3 <= N <= 35). The towns are denoted by 1, 2, ..., N. There are direct routes connecting M pairs from among these towns. The company decides to build servicing stations in several towns, so that for any town X, there would be a station located either in X or in some immediately neighbouring town of X.

Write a program for finding out the minumum number of stations, which the company has to build, so that the above condition holds.

Input
The input consists of more than one description of town (but totally, less than ten descriptions). Every description starts with number N of towns and number M of pairs of towns directly connected each other. The integers N and M are separated by a space. Every one of the next M rows contains a pair of connected towns, one pair per row. The pair consists of two integers for town's numbers, separated by a space. The input ends with N = 0 and M = 0. Output
For every town in the input write a line containing the obtained minimum.

An example:

Input:

8 12
1 2
1 6
1 8
2 3
2 6
3 4
3 5
4 5
4 7
5 6
6 7
6 8
0 0

Output:

2


沒加估價函數,程序居然也會過,情何以堪啊!
而且跑得也不差,怒加常數!
-----
Final:4.085 s -> 0.012 s,Rank 394 -> Rank 21
[NPC 問題] 圖的最小支配點集

常數加多少,取決於測資,簡單來說就是在衝假解。


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Maxv 100000
using namespace std;
struct DacingLinks {
    int left, right;
    int up, down;
    int data, ch, rh;
}DL[5000];
int s[40], o[40], head, size, Ans;
void Remove(int c) {
    static int i;
    for(i = DL[c].down; i != c; i = DL[i].down) {
        DL[DL[i].right].left = DL[i].left;
        DL[DL[i].left].right = DL[i].right;
        s[DL[i].ch]--;
    }
}
void Resume(int c) {
    static int i;
    for(i = DL[c].down; i != c; i = DL[i].down) {
        DL[DL[i].right].left = i;
        DL[DL[i].left].right = i;
        s[DL[i].ch]++;
    }
}
int used[40] = {};
int H() {
    static int c, ret, i, j, time = 0;
    for(c = DL[head].right, ++time, ret = 0; c != head; c = DL[c].right) {
        if(used[c] != time) {
            ret ++, used[c] = time;
            for(i = DL[c].down; i != c; i = DL[i].down)
                for(j = DL[i].right; j != i; j = DL[j].right)
                    used[DL[j].ch] = time;
        }
    }
    return ret;
}
void DFS(int k) {
    if(k + H()*2 >= Ans)    return; // H()*? guess.
    if(DL[head].right == head) {
        if(k < Ans)    Ans = k;
        return;
    }
    int t = Maxv, c, i, j;
    for(i = DL[head].right; i != head; i = DL[i].right) {
        if(s[i] < t) {
            t = s[i], c = i;
        }
    }
    for(i = DL[c].down; i != c; i = DL[i].down) {
        Remove(i);
        for(j = DL[i].right; j != i; j = DL[j].right)    Remove(j);
        DFS(k+1);
        for(j = DL[i].left; j != i; j = DL[j].left)        Resume(j);
        Resume(i);
    }
}
int new_node(int up, int down, int left, int right) {
    DL[size].up = up, DL[size].down = down;
    DL[size].left = left, DL[size].right = right;
    DL[up].down = DL[down].up = DL[left].right = DL[right].left = size;
    return size++;
}
void new_row(int n, int Row[]) {
    int a, r, row = -1, k;
    for(a = 0; a < n; a++) {
        r = Row[a];
        DL[size].ch = r, s[r]++;
        if(row == -1) {
            row = new_node(DL[DL[r].ch].up, DL[r].ch, size, size);
            DL[row].rh = a;
        }else {
            k = new_node(DL[DL[r].ch].up, DL[r].ch, DL[row].left, row);
            DL[k].rh = a;
        }
    }
}
void init(int m) {
    size = 0;
    head = new_node(0, 0, 0, 0);
    int i;
    for(i = 1; i <= m; i++) {
        new_node(i, i, DL[head].left, head);
        DL[i].ch = i, s[i] = 0;
    }
}
int main() {
    int n, m;
    /*freopen("in.txt", "r+t", stdin);
    freopen("out2.txt", "w+t", stdout);*/
    while(scanf("%d %d", &n, &m) == 2) {
        if(n == 0 && m == 0)
            break;
        int i, j;
        int g[40][40] = {}, x, y;
        for(i = 1; i <= m; i++) {
            scanf("%d %d", &x, &y);
            g[x][y] = 1;
            g[y][x] = 1;
        }
        init(n);
        int row[500], nt;
        for(i = 1; i <= n; i++) {
            nt = 0;
            for(j = 1; j <= n; j++) {
                if(j == i || g[i][j])
                    row[nt++] = j;
            }
            new_row(nt, row);
        }
        Ans = Maxv;
        DFS(0);
        printf("%d\n", Ans);
    }
    return 0;
}

10160Servicing StationsDLX最少重覆覆蓋
台長:Morris
人氣(23) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][spfa] 10967 - The Great Escape
此分類上一篇:[UVA][dfs] 776 - Monkeys in a Regular Forest

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文