Holes Gym - 100519H（二分，图论）

admin管理员组

文章数量:1594753

In this problem, we investigate the life of rabbits.

Our rabbits live in the glades, some of which are connected with two-way trails. No trail makes a loop: each of them connects two different glades. There is at most one trail between any pair of glades.

Our rabbits can dig holes in the ground where they can hide in case of danger. The holes can be dug in the center of each glade. In order for the rabbit to hide in the hole, the rabbit just needs to get to the glade where the hole is located, and then it hides there immediately. Each hole can accommodate any number of rabbits.

The rabbit universe has two important features: there is a path between any two glades, and each glades except at most one is connected with no more than two other glades.

Rabbits want to make some holes so that in case of danger, they can minimize the time for all rabbits to hide. Help them find the right glades to dig the holes. The time is calculated as a number of trails a rabbit uses to get to the hole. All rabbits are traveling and hiding independently.

It is also assumed that there are so many rabbits that each glade has at least one of them.

Input
The first line of input contains integers N, M and K: the number of glades, the number of trails and the number of holes to be dug respectively (1 ≤ K ≤ N ≤ 1000).

Each of the next M lines describes one trail and contains two integers x i and y i: the numbers of glades that are connected by this trail (1 ≤ x i, y i ≤ N).

Output
Output a single integer: the minimum possible amount of time needed for all rabbits to hide in case all K holes are placed optimally.

Examples
Input
5 6 1
3 1
3 2
3 4
3 5
1 2
4 5
Output
1
Input
8 8 2
1 2
2 3
3 4
4 1
1 5
5 6
6 7
7 8
Output
2

题意：
一个图，最多只有一个点度数大于2。可以放 k k k个房子，每个点要去一个房子，求所有点找到房子的最小时间。

思路：
将最大度数的点当做根节点，则根节点出发要么成环回到根节点，要么就是一条直链。

二分这个最大距离，然后算最少需要多少个房子。
可以想到，在一个房子，最多影响 2 ∗ x + 1 2*x+1 2∗x+1个点，策略是放到中间

先一遍 d f s dfs dfs求出所有直线和环的大小。

对于直链与环分别考虑。

m x 1 mx1 mx1代表根节点最多延伸多少个点
m x 2 mx2 mx2代表距根节点最多多少个点没覆盖到

初始化 m x 1 = − 1 , m x 2 = − 1 mx1=-1,mx2=-1 mx1=−1,mx2=−1
当 m x 1 = 0 mx1=0 mx1=0时代表根节点被延伸到
当 m x 2 = 0 mx2=0 mx2=0时代表根节点没覆盖到

一个直线必须的房子数为： l i n e [ i ] / ( 2 ∗ m i d + 1 ) line[i] / (2 * mid + 1) line[i]/(2∗mid+1)
设 r e s = l i n e [ i ] m o d    ( 2 ∗ m i d + 1 ) res = line[i] \mod (2 * mid + 1) res=line[i]mod(2∗mid+1)

如果 r e s > m i d + 1 res>mid+1 res>mid+1，则这个直线上必须再放一个房子，最后根节点往外延伸的点数为 2 ∗ m i d + 1 − r e s 2 * mid + 1 - res 2∗mid+1−res。
如果 r e s = 0 res=0 res=0，则代表根节点被延伸到了，所以 m x 1 = m a x ( m x 1 , 0 ) mx1=max(mx1,0) mx1=max(mx1,0)
否则，则剩下了没覆盖到的点，所以 m x 2 = m a x ( m x 2 , r e s − 1 ) mx2=max(mx2,res-1) mx2=max(mx2,res−1)

对于环也是这是类似的考虑，但是比较特殊的是，当有 c i r c l e [ i ] m o d    ( 2 ∗ m i d + 1 ) circle[i] \mod(2 * mid + 1) circle[i]mod(2∗mid+1)时，代表肯定根节点肯定要放房子（这个环要一开始被全覆盖，根节点放上房子显然更优），那么每个环的需要放的房子数位 c i r c l e [ i ] / ( 2 ∗ m i d + 1 ) − 1 ; circle[i] / (2 * mid + 1) - 1; circle[i]/(2∗mid+1)−1;，减去的1为根节点的房子数，最后再加上。

最后考虑根节点上要不要放房子：假设 m x 2 = − 1 mx2=-1 mx2=−1，代表没有点没被覆盖到，则不用算。否则比较 m x 2 mx2 mx2和 m x 1 mx1 mx1，如果 m x 2 > m x 1 mx2>mx1 mx2>mx1，则延伸的部分不能抵消覆盖的部分，那么根节点一定要放房子。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <string>
#include <iostream>
#include <cmath>

using namespace std;
typedef long long ll;

const int maxn = 1000 + 7;

int n,m,k;
vector<int>G[maxn];
int line[maxn],circle[maxn],vis[maxn];
int cnt1,cnt2;

void dfs(int u,int fa,int rt,int d) {
    if(G[u].size() == 1) {
        line[++cnt1] = d;
        return;
    }
    for(int i = 0;i < G[u].size();i++) {
        int v = G[u][i];
        if(v == fa) continue;
        if(v == rt) {
            circle[++cnt2] = d;
            return;
        }
        if(vis[v]) continue;
        vis[v] = 1;
        dfs(v,u,rt,d + 1);
    }
}

bool check(int mid) {
    int cost = 0;
    int mx1 = -1; //根节点最多延伸多少个点
    int mx2 = -1; //距根节点最多多少个点没覆盖到
    
    //mx1如果为0代表延伸到了根节点，如果为-1代表没延伸到根节点
    //mx2如果为0代表根节点没有覆盖到，mx2如果为-1代表所有点都覆盖到了。
    
    for(int i = 1;i <= cnt1;i++) {
        cost += line[i] / (2 * mid + 1);
        int res = line[i] % (2 * mid + 1);
        if(res - 1 > mid) {
            cost++;
            mx1 = max(mx1,2 * mid + 1 - res); //最远往外延伸多少
        }
        else if(res == 0) {
            mx1 = max(mx1,0);
        }
        else {
            mx2 = max(mx2,res - 1); //算出剩余点离根节点的最远距离
        }
    }
    
    for(int i = 1;i <= cnt2;i++) {
        if(circle[i] % (2 * mid + 1) == 0) {
            cost += circle[i] / (2 * mid + 1) - 1; //因为最后要用根节点，这里暂时不用
            mx2 = max(mx2,mid); //表示一定要用根节点
        } else {
            cost += circle[i] / (2 * mid + 1);
            int res = circle[i] % (2 * mid + 1);
            mx2 = max(mx2,res / 2);
        }
    }
    
    if(mx2 != -1 && mx2 > mx1) {
        cost++;
    }
    return cost <= k;
}

int main() {
    scanf("%d%d%d",&n,&m,&k);
    int rt = 1,mx = 0;
    for(int i = 1;i <= m;i++) {
        int x,y;scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
        if(G[x].size() > mx) {
            mx = G[x].size();
            rt = x;
        }
        if(G[y].size() > mx) {
            mx = G[y].size();
            rt = y;
        }
    }
    if(k >= n) {
        printf("0");
        return 0;
    }
    dfs(rt,-1,rt,1);
    
    int l = 1,r = n;
    int ans = n;
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    printf("%d\n",ans);
    return 0;
}

本文标签： 图论HolesGym