TJOI2018 Day1 T2

TJOI2018 Day1 T2

​​ 给定一个DAG 可以用n+1条路径覆盖求不能覆盖的点中最小值最大

出题人的语文水平+elijahqi的语文水平为负无穷 读错题只有10分系列

考虑二分答案 然后二分图匹配 求最小可相交路径覆盖问题

注意二分答案的单调性 即 若3->6之间有一个8 然而这次二分的答案是7 他们这条边也应该视为存在

#include#include#include#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int inf=0x3f3f3f3f;const int N=550;struct node{ int y,next;}data[N*N];int h[N],g[N],num,v[N],n,m;bool mp[N][N],mp1[N][N],used[N];inline bool find(int x){ for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (used[y]) continue;used[y]=1; if (!g[y]||find(g[y])){ g[y]=x;return 1; } }return 0;}inline void insert1(int x,int y){ data[++num].y=y;data[num].next=h[x];h[x]=num;}inline bool check(int md){ memset(mp1,0,sizeof(mp1)); memset(h,0,sizeof(h));num=0; for (int i=1;i<=m;++i){ for (int j=1;j<=m;++j){ if (v[i]<=md&&v[j]<=md&&mp[i][j]) mp1[i][j]=1; } }int ans=0; for (int k=1;k<=m;++k) for (int i=1;i<=m;++i){ if (!mp1[i][k]) continue; for (int j=1;j<=m;++j) mp1[i][j]|=mp1[i][k]&mp1[k][j]; } for (int i=1;i<=m;++i){ if (v[i]<=md) ++ans;else continue; for (int j=1;j<=m;++j){ if (mp1[i][j]) insert1(i,j); } }memset(g,0,sizeof(g)); for (int i=1;i<=m;++i){ if (v[i]>md) continue; memset(used,0,sizeof(used)); if (find(i)) --ans; } return ans<=n;}int main(){ freopen("contest.in","r",stdin); freopen("contest.out","w",stdout); n=read()+1;m=read();int l=inf,r=0; for (int i=1;i<=m;++i){ v[i]=read();int k=read();l=min(l,v[i]);r=max(r,v[i]); for (int j=1;j<=k;++j) mp[i][read()]=1; } for (int k=1;k<=m;++k){ for (int i=1;i<=m;++i){ if (!mp[i][k]) continue; for (int j=1;j<=m;++j){ if (i==j) continue; mp[i][j]|=mp[i][k]&mp[k][j]; } } } int mx=r; while(l<=r){ int mid=l+r>>1; if (check(mid)) l=mid+1;else r=mid-1; } if (l>mx) puts("AK");else printf("%d\n",l); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。