2018-04-29

gym补题

挂机四个半小时。。。

D effective network

构造题

题意

首先从这个无向图中选出来q个点，然后这q个点之间任意两点之间的距离不能超过q-k

题解

比赛的时候用最短路来维护任意两点之间的距离，然后判断。
因为最短路的时间复杂度为\(O(n^2log(n))\)的预处理，然后二分的寻找q值， \(O(n^3)\)的时间复杂度的寻找判断。结果一直T。。。

后来看了解答。利用了一个性质：
若原来的图中存在一个解，那么整张图也满足原来的性质。

如果对于x个点（x<=n）存在x-k>=max，那么x增加一个点。那么最大的距离最大为max+1。那么 (x+1)-k>=(max+1) 依然成立。所以增加到n也是成立的。并且再实际情况中 max并不一定会增加1。这时考虑最差的情况。

然后用bfs对每一个点判断就行了

#include <bits/stdc++.h>
using namespace std;
const int maxn  = 5000+10;
int d[maxn];
bool vis[maxn];
vector<int> G[maxn];
int n, m, k;
void init(){
    for(int i=0; i<maxn; i++) G[i].clear();
}
int bfs(int u){
    memset(vis, 0, sizeof(vis));
    memset(d, 0, sizeof(d));
    vis[u] = true;
    queue<int> q;
    q.push(u);
    while(!q.empty()){
        int temp = q.front();
        q.pop();
        for(int i=0; i<G[temp].size(); i++){
            int v = G[temp][i];
            if(vis[v]) continue;
            else{
                d[v] = d[temp]+1;
                vis[v] = true;
                q.push(v);
            }
        }
    }
    int max_depth = -1;
    for(int i=1; i<=n; i++){
        max_depth = max(max_depth, d[i]);
    }
    return max_depth;
}
int main(){
    while(cin>>n>>m>>k){
        init();
        int u, v;
        for(int i=0; i<m; i++){
            cin>>u>>v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        int ans = -1;
        for(int i=1; i<=n; i++){
            int temp = bfs(i);
            ans = max(ans, temp);
        }
        if(ans<=n-k){
            cout<<n<<endl;
            for(int i=1; i<=n; i++){
                i == 1?cout<<1:cout<<" "<<i;
            }
            cout<<endl;
        }
        else cout<<0<<endl;
    }
    return 0;
}

后来发现直接判断规模为n的思想是真的非常的重要啊！
用dij堆优化也能过，用了3837ms,前面的bfs用了1419ms.

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5000+10;
const int maxm = 3e4+10;
const int INF = 0x3f3f3f3f;
int dis_all[maxn][maxn];
bool vis[maxn];
int dis[maxn];
int n, m, k;
struct Node{
    int v, cost;
    Node(int _v = 0, int _cost = 0):v(_v), cost(_cost){}
};
struct qnode{
    int v, c;
    qnode(int _v=0, int _c=0):v(_v), c(_c){}
    bool operator < (const qnode &r) const {
        return c>r.c;
    }
};
vector<Node> G[maxn];
void init(){
    for(int i=0; i<maxn; i++) G[i].clear();
}
void dij(int s){
    memset(vis, 0, sizeof(vis));
    for(int i=0; i<maxn; i++) dis[i] = INF;
    priority_queue<qnode> pq;
    dis[s] = 0;
    pq.push(qnode(s, 0));
    qnode temp;
    while(!pq.empty()){
        temp = pq.top();
        pq.pop();
        int u = temp.v;
        if(vis[u]) continue;
        vis[u] = true;
        for(int i=0; i<G[u].size(); i++){
            Node e = G[u][i];
            int v = e.v;
            int cost = e.cost;
            if(!vis[v] && dis[v]>dis[u]+cost){
                dis[v] = dis[u]+cost;
                pq.push(qnode(v, dis[v]));
            }
        }
    }
}
int main(){
	ios :: sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    while(cin>>n>>m>>k){
        init();
        for(int i=0; i<m; i++){
            int u, v;
            cin>>u>>v;
            G[u].push_back(Node{v, 1});
            G[v].push_back(Node{u, 1});
        }
        int ans = -1;
        for(int i=1; i<=n; i++){
            dij(i);
            for(int j=1; j<=n; j++){
                dis_all[i][j] = dis[j];
                ans = max(ans, dis[j]);
            }
        }
        bool flag = true;
        if(n-k<ans) flag = false;
        if(!flag){
            cout<<0<<endl;
        }
        else{
            cout<<n<<endl;
            for(int i=1; i<=n; i++){
                i == 1?cout<<1:cout<<" "<<i;
            }
            cout<<endl;
        }
    }
    return 0;
}

未解决的问题

本文标题:gym补题

文章作者:Babydragon

发布时间:2018-04-29, 16:23:09

最后更新:2018-04-29, 16:52:42

原始链接:http://baolintian.github.io/2018/04/29/gym补题/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。