BZOJ3346 : Ural1811 Dual Sim Phone
Phone Dual
2023-09-11 14:15:04 时间
首先将边进行去重,那么有$n\geq\sqrt{m}$。
然后二分答案,转化为判定是否存在两个点它们的出边集合的并集为全集。
那么这两个点必然满足$deg_x+deg_y\geq n$。
不妨设$deg_x\geq deg_y$,那么有$deg_x\times 2\geq n$。
考虑枚举$x$,最多只会有$O(\frac{m}{n})$个$x$。
再枚举$y$,有两种判定算法:
$1.$设$f[i][j]$表示$i$是否没有指向$j$,那么只要存在$f[x][j]\ and\ f[y][j]=true$即不可行。
可以压位计算,时间复杂度$O(\frac{nm}{32})$。
$2.$枚举$y$的所有出边,通过时间戳判定是否出现在$x$中。
时间复杂度$O(\frac{m^2}{n})$。
设$S$为阈值,当$n\leq S$时用算法1,否则用算法2,则有$\frac{Sm}{32}\leq\frac{m^2}{S}$。
当$S$取$\sqrt{32m}$时,取得最优复杂度$O(m\sqrt{\frac{m}{32}})$。
总时间复杂度$O(m\log m\sqrt{\frac{m}{32}})$。
#include<cstdio> #include<algorithm> const int N=10005,M=100010; int n,m,U,i,j,k,a[M],st[N],en[N],d[N],v[N],t,l,r,mid,ans; unsigned int f[2048][64]; struct E{int x,y,z;}e[M]; inline bool cmp(const E&a,const E&b){ if(a.x!=b.x)return a.x<b.x; if(a.y!=b.y)return a.y<b.y; return a.z<b.z; } inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';} bool check(int mid){ if(n>2048){ for(i=0;i<n;i++){ d[i]=0; for(j=st[i];j<en[i];j++)if(e[j].z<=mid)d[i]++; } for(i=0;i<n;i++)v[i]=-1; for(i=0;i<n;i++)if(d[i]*2>=n){ for(k=st[i];k<en[i];k++)if(e[k].z<=mid)v[e[k].y]=i; for(j=0;j<n;j++)if(d[i]+d[j]>=n&&d[i]>=d[j]){ t=d[i]; for(k=st[j];k<en[j];k++)if(e[k].z<=mid&&v[e[k].y]<i)t++; if(t==n)return 1; } } }else{ for(i=0;i<n;i++){ for(j=0;j<U;j++)f[i][j]=~0U; f[i][U]=0; for(j=U<<5;j<n;j++)f[i][j>>5]|=1U<<(j&31); } for(i=0;i<n;i++){ d[i]=0; for(j=st[i];j<en[i];j++)if(e[j].z<=mid)d[i]++,f[i][e[j].y>>5]^=1U<<(e[j].y&31); } for(i=0;i<n;i++)if(d[i]*2>=n){ for(j=0;j<n;j++)if(d[i]+d[j]>=n&&d[i]>=d[j]){ t=1; for(k=0;k<=U;k++)if(f[i][k]&f[j][k]){t=0;break;} if(t)return 1; } } } return 0; } int main(){ read(n),read(m);U=(n-1)>>5; for(i=1;i<=m;i++){ read(e[i].x),read(e[i].y),read(e[i].z); e[i].x--,e[i].y--; } std::sort(e+1,e+m+1,cmp); for(i=1;i<=m;i++)if(i==1||e[i].x!=e[i-1].x||e[i].y!=e[i-1].y)e[++j]=e[i]; for(m=j,i=1;i<=m;i++)a[i]=e[i].z; std::sort(a+1,a+m+1); for(i=0,j=1;i<n;i++){ st[i]=j; while(j<=m&&e[j].x==i)j++; en[i]=j; } l=1,r=m; while(l<=r)if(check(a[mid=(l+r)>>1]))r=(ans=mid)-1;else l=mid+1; if(!ans)puts("No solution");else printf("%d",a[ans]); return 0; }
相关文章
- Timus : 1002. Phone Numbers 题解
- zoj 2876 Phone List
- 1016 Phone Bills (25 分) 【未完成】【难度: 中 / 知识点: 模拟】
- 课程上线 -“新手入门 : Windows Phone 8.1 开发”
- Windows Phone Studio-任何人都能开发Windows Phone App的在线工具
- Windows Phone 8.0 SDK Update(10322) Released
- Windows Phone-框架结构和启动过程
- Windows Phone开发工具初体验【转载】
- WhartonBrooks将为Windows Phone市场注入新的活力
- Android、iOS和Windows Phone中的推送技术
- nyoj 163 Phone List(动态字典树<trie>) poj Phone List (静态字典树<trie>)
- Windows Phone 版 Cocos2d-x 程序的结构
- 使用 Cocos2d-x 3.1.1 创建 Windows Phone 8 游戏开发环境
- [LintCode] Letter Combinations of a Phone Number 电话号码的字母组合