Massive Algorithms: UVA 10859 - Placing Lampposts

Placing Lampposts

As a part of the mission �Beautification of Dhaka City�, the government has decided to replace all the old lampposts with new expensive ones. Since the new ones are quite expensive and the budget is not up to the requirement, the government has decided to buy the minimum number of lampposts required to light the whole city.

Dhaka city can be modeled as an undirected graph with no cycles, multi-edges or loops. There are several roads and junctions. A lamppost can only be placed on junctions. These lampposts can emit light in all the directions, and that means a lamppost that is placed in a junction will light all the roads leading away from it.

The �Dhaka City Corporation� has given you the road map of Dhaka city. You are hired to find the minimum number of lampposts that will be required to light the whole city. These lampposts can then be placed on the required junctions to provide the service. There could be many combinations of placing these lampposts that will cover all the roads. In that case, you have to place them in such a way that the number of roads receiving light from two lampposts is maximized.

Input

There will be several cases in the input file. The first line of input will contain an integer T(T<=30) that will determine the number of test cases. Each case will start with two integers N(N<=1000) and M( M<N) that will indicate the number of junctions and roads respectively. The junctions are numbered from 0 to N-1. Each of the next M lines will contain two integers a and b, which implies there is a road from junction a to b,
( 0<= a,b < N ) and a != b. There is a blank line separating two consecutive input sets.

Output

For each line of input, there will be one line of output. Each output line will contain 3 integers, with one space separating two consecutive numbers. The first of these integers will indicate the minimum number of lampposts required to light the whole city. The second integer will be the number of roads that are receiving lights from two lampposts and the third integer will be the number of roads that are receiving light from only one lamppost.

Sample Input

2
4 3
0 1
1 2
2 35 4
0 1
0 2
0 3
0 4

Sample Output

2 1 2
1 0 4

http://blog.csdn.net/shuangde800/article/details/9899265
思路
这是LRJ《训练指南》上的例题。
这题教会了我一个很有用的技巧：有两个所求的值要优化，比如让a尽量小，ｂ也尽量小
那么可以转化为让 M*a+b尽量小，其中Ｍ应该是一个比“a的最大值和b的最小值之差”还要大的数
最终的答案为ans/M, ans%M

回到这题，要求放的灯总数最小，被两盏灯同时照亮的边数尽量大。
因为每条边要么被一盏灯照亮，要么被两盏灯照亮，所以可以转换为：
求：放的灯总数量最少，被一盏灯照亮的边数尽量少。
就可以变成球 M*a+b 的最小值，ａ为放置的灯数量，ｂ为被一盏灯照的边数

f[u][1]表示u点放灯时的整个子树最小值
f[u][0]表示u点不放灯时的整个子树最小值

如果u放，那么u个子结点可以选择放，也可以不放，选择其中较小的值。如果选的是不照，就要增加一条只有一个灯照的边
如果u不放，那么其子结点就必须选择要放，而且每条边都只有一个灯照

http://blog.csdn.net/keshuai19940722/article/details/19363649
每次枚举某个顶点作为根，对于每个点有放与不放两种可能，均进行考虑；然后每放一盏灯+2000（因为边的最大数量为1000），每增加1条照亮一次的边+1.

http://www.cnblogs.com/czjxy881/p/3536007.html

1.统一化目标，本题需要优化目标有两个，一个最小灯数a，一个最大双覆盖边数b，一大一小，应该归一成，a及单覆盖边数c，

x=Ma+c 为最小化目标，

M>Δc

2.决策分析，只有两种放灯与不放，如不放灯则需要父节点必须放灯，故需要父节点状态，设

f(i,j)为节点i在父节点状态为j时的最小x值，j为0代表不放灯，j为1代表放

{sum{d(k,0)|k为i所有子节点}+(i为根节点?0:1)sum{d(k,1)|k为i所有子节点}+M+(i不为根节点且j==0?1:0),i不放灯,i 放灯

http://blog.csdn.net/shuangde800/article/details/9899265


const int INF = 0x3f3f3f3f;



const int MAXN = 1010;

vector<int>adj[MAXN];

bool vis[MAXN];

int n, m;

int f[MAXN][2];

const int M = 2000;



void dfs(int u) {

    vis[u] = true;

    f[u][0] = 0;

    f[u][1] = M;

    for(int i = 0; i < adj[u].size(); ++i) {

        int v = adj[u][i]; 

        if(vis[v]) continue;

        dfs(v);

        f[u][0] += f[v][1] + 1;

        if (f[v][0] < f[v][1]) {

            f[u][1] += f[v][0] + 1;

        } else {

            f[u][1] += f[v][1];

        } 

    }

}



int main(){



    int nCase;



    scanf("%d", &nCase);



    while(nCase--) {



        scanf("%d%d", &n, &m);



        for(int i = 0; i < n; ++i) 

            adj[i].clear();



        for(int i = 0; i < m; ++i) {

            int u, v;

            scanf("%d%d", &u, &v);

            adj[u].push_back(v);

            adj[v].push_back(u);

        }



        memset(vis, 0, sizeof(vis));

        int ans = 0;

        for(int i = 0; i < n; ++i) if(!vis[i]){

            dfs(i);

            ans += min(f[i][0], f[i][1]);

        }

        printf("%d %d %d\n", ans/M, m-(ans%M), ans%M);

    }



    return 0;

}

Also check code at http://blog.csdn.net/u011686226/article/details/18449841

UVA 10859 - Placing Lampposts

Placing Lampposts

Labels

Popular Posts