A simple Blog for wyx I've been down the bottle hoping.
BZOJ3346 : Ural1811 Dual Sim Phone
发表于: | 分类: Oi | 评论:0 | 阅读:60

这题的思路很棒棒啊……

考虑先把所有边去重,多个$a,b$间的边只保留权值最小的,那么新图最坏情况下就是$n^2$条边

然后传统套路二分答案,问题变成两个点使得他们的出边边集是全集

考虑这样一个问题,两个点的出度之和必然$>= n$,那么对于一个度数较大的点必然$>= \frac{n}{2}$

注意到这样的点最多只有$\frac{m}{n}$个,然后$O(n)$大力枚举一下另外一个点,考虑下面两个算法


1.考虑求出两个点对于这个图的反图,如果存在点使得两个点都向其连边则说明不可行。注意到邻接矩阵可以直接通过&运算玩出来,大力压位后复杂度为$O(\frac{nm}{32})$

2.考虑直接枚举两个点的出点集合是否是全集,显然是可以通过标记判断本质不同的出点一共有多少个的复杂度$O(\frac{m^2}{n})$

注意到一个$n$在分母上一个$n$在分子上,所以当$n$小的时候用算法1,$n$大的时候用算法2

然后复杂度显然是二者取到相等的时候的取值,此时$n=\sqrt{32m}$

所以总复杂度是$O(m\log (m\sqrt{\frac{m}{32}}))$

牛逼的外国构造气息

#include <vector>
#include <bitset>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10000+5;
const int M = 10 * N;
typedef bitset<N> Int;
Int F[N], standerd;
int n, m, tim[N], deg[N], a[M];

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

struct data{
    int x, y, val;
    bool operator<(const data &z) const{
        if(x != z.x) return x < z.x;
        if(y != z.y) return y < z.y;
        return val < z.val;
    } 
    bool operator != (const data &z) const {
        return x != z.x || y != z.y;
    }
} edge[M];

vector <int> V[N];

inline bool check(int mid) {
    static const int base = 2050;
    if(n > base) {
        for(int i=1;i<=n;++i) {
            deg[i] = 0;
            for(int j=0;j<V[i].size();++j) {
                int temp = V[i][j];
                if(edge[temp].val <= mid) deg[i] ++;
            }
        }
        for(int i=1;i<=n;++i) tim[i] = -1;
        for(int i=1;i<=n;++i) if(deg[i]*2>=n){
            for(int j=0;j<V[i].size();++j) {
                int temp = V[i][j];
                if(edge[temp].val <= mid) tim[edge[temp].y] = i;
            }
            for(int j=1;j<=n;++j) if(deg[i] + deg[j] >= n && deg[i] >= deg[j]) {
                int temp = deg[i];
                for(int k=0;k<V[j].size();++k) {
                    int temp2 = V[j][k];
                    if(edge[temp2].val <= mid && tim[edge[temp2].y] < i) temp ++;
                }
                if(temp == n) return true;
            }
        }
    }
    else {
        for(int i=1;i<=n;++i) F[i] = standerd;
        for(int i=1;i<=n;++i) {
            deg[i] = 0;
            for(int j=0;j<V[i].size();++j) {
                int temp = V[i][j];
                if(edge[temp].val <= mid) {
                    deg[i] ++;
                    F[i].reset(edge[temp].y);
                }
            }
        //  cout << F[i] << endl;
        }
        for(int i=1;i<=n;++i) if(deg[i] * 2 >= n){
            for(int j=1;j<=n;++j) if(deg[j] + deg[i] >= n && deg[i] >= deg[j]) {
                Int temp = F[i]&F[j];
                if(!temp.any()) return true;
            }
        }
    }
    return false;
}

int main() {
//  freopen("tt.in","r",stdin);
    n = read(), m = read();
    for(int i=1;i<=n;++i) standerd.set(i);
    for(int i=1;i<=m;++i) {
        edge[i].x = read(), edge[i].y = read(), edge[i].val = read();
    }
    sort(edge+1,edge+m+1);
    int top = 1;
    for(int i=2;i<=m;++i) if(edge[i] != edge[i-1]) edge[++top] = edge[i];
    m = top;
    for(int i=1;i<=m;++i) a[i] = edge[i].val;   
    sort(a+1,a+m+1);
    for(int i=1;i<=m;++i) V[edge[i].x].push_back(i);
    int l = 1, r = m + 1;
    while(l<r) {
        int mid = (l+r) >> 1;
        if(check(a[mid])) r = mid;
        else l = mid + 1;
    }
    if(l ==  m + 1) puts("No solution");
    else cout << a[l] << endl;
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP