[关闭]
@ysner 2018-10-30T11:57:04.000000Z 字数 5211 阅读 2209

[noip模拟赛]午餐

最短路 贪心

题面

林先森发现很多同学突然学会了毒瘤算法,他决定调查一下这是怎么一回事。
一共有个人,林先森知道开始时只有号会毒瘤算法。林先森了解到很多人一起吃过
午餐;具体地,有条信息,其中第条信息描述和在区间中的某一天一起吃
了午餐。若此时或中的一个人会毒瘤算法,那么两个人都能学会毒瘤算法。特别地,若
一个人在某天和多个人一起吃午餐,那么他在学会毒瘤算法的同时会立即教给别人(同一天的
午餐均视作同时发生)。
林先森知道最后学会了毒瘤算法的同学以及没有学会毒瘤算法的同学,以及一些不确定是
否学会了毒瘤算法的同学。林先森想知道大家具体在哪一天共用了午餐,或者告诉林先森这样
的结果是不可能出现的。

解析

做难题从部分分开始。

算法

显然，如果有这条性质，可以推个贪心结论：每个人尽早学会毒瘤算法肯定是最优的。
所以可以设表示第个人最早学会毒瘤算法的时间。


然后发现转移等价于最短路。
那么拿跑一跑就行。

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<algorithm>
  7. #include<queue>
  8. #define ll long long
  9. #define re register
  10. #define il inline
  11. #define pi pair<int,int>
  12. #define mk make_pair
  13. #define fi first
  14. #define se second
  15. #define fp(i,a,b) for(re int i=a;i<=b;++i)
  16. #define fq(i,a,b) for(re int i=a;i>=b;--i)
  17. using namespace std;
  18. const int N=20,M=2e5+100;
  19. int n,m,cho[N],tar[M],top[N],mx,tag=1;
  20. struct dat{int u,v,L,R;}a[M],sta[10][N];
  21. bool vis[M];
  22. int h[M],cnt,dis[M];
  23. struct Edge{int to,nxt,mn,mx;}e[M<<1];
  24. il void add(re int u,re int v,re int mn,re int mx)
  25. {
  26.   e[++cnt]=(Edge){v,h[u],mn,mx};h[u]=cnt;
  27.   e[++cnt]=(Edge){u,h[v],mn,mx};h[v]=cnt;
  28. }
  29. il ll gi()
  30. {
  31.   re ll x=0,t=1;
  32.   re char ch=getchar();
  33.   while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  34.   if(ch=='-') t=-1,ch=getchar();
  35.   while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  36.   return x*t;
  37. }
  38. il void out()
  39. {
  40.   fp(i,1,m) printf("%d\n",cho[i]);
  41.   exit(0);
  42. }
  43. il void check()
  44. {
  45.   fp(i,1,n) vis[i]=0;vis[1]=1;
  46.   fp(i,1,mx)
  47.     {
  48.       fp(j,1,top[i]) if(vis[sta[i][j].u]||vis[sta[i][j].v]) vis[sta[i][j].u]=vis[sta[i][j].v]=1;
  49.       fp(j,1,top[i]) if(vis[sta[i][j].u]||vis[sta[i][j].v]) vis[sta[i][j].u]=vis[sta[i][j].v]=1;
  50.     }
  51.   re int tag=1;
  52.   fp(i,1,n) if((tar[i]==1&&!vis[i])||(tar[i]==-1&&vis[i])) {tag=0;break;}
  53.   if(tag) out();
  54. }
  55. il void dfs(re int x)
  56. {
  57.   if(x>m) {check();return;}
  58.   fp(i,a[x].L,a[x].R)
  59.     {
  60.       mx=max(mx,a[x].R);
  61.       cho[x]=i;
  62.       sta[i][++top[i]]=a[x];
  63.       dfs(x+1);
  64.       --top[i];
  65.     }
  66. }
  67. il int min(re int x,re int y){return x<y?x:y;}
  68. il int max(re int x,re int y){return x>y?x:y;}
  69. il void Dijstra()
  70. {
  71.   priority_queue<pi,vector<pi>,greater<pi> >Q;
  72.   while(!Q.empty()) Q.pop();
  73.   fp(i,1,n) vis[i]=0,dis[i]=1e9+7;
  74.   dis[1]=0;Q.push(mk(0,1));
  75.   while(!Q.empty())
  76.     {
  77.       re int u=Q.top().se;Q.pop();
  78.       vis[u]=1;
  79.       for(re int i=h[u];i+1;i=e[i].nxt)
  80.     {
  81.       re int v=e[i].to,mx=e[i].mx,mn=e[i].mn;
  82.       if(dis[v]>max(mn,dis[u])&&dis[u]<=mx)
  83.         {
  84.           dis[v]=max(mn,dis[u]);
  85.           Q.push(mk(dis[v],v));
  86.         }
  87.     }
  88.       while(!Q.empty()&&vis[Q.top().se]) Q.pop();
  89.     }
  90. }
  91. il void solve()
  92. {
  93.   memset(h,-1,sizeof(h));
  94.   fp(i,1,m) add(a[i].u,a[i].v,a[i].L,a[i].R);
  95.   Dijstra();
  96.   fp(i,1,n) if(tar[i]==1&&dis[i]>1e9) {puts("Impossible");exit(0);}
  97.   fp(i,1,m) printf("%d\n",dis[a[i].u]>a[i].R?a[i].L:max(a[i].L,dis[a[i].u]));
  98.   exit(0);
  99. }
  100. int main()
  101. {
  102.   n=gi();m=gi();
  103.   fp(i,1,m)
  104.     {
  105.       a[i].u=gi(),a[i].v=gi(),a[i].L=gi(),a[i].R=gi();
  106.     }
  107.   fp(i,1,n) tar[i]=gi(),tag&=(tar[i]>=0);
  108.   if(n>12&&tag) solve();//for ex35pts
  109.   dfs(1);//for 10pts
  110.   puts("Impossible");
  111.   return 0;
  112. }

算法

直接想是有难度的。
但有作为铺垫就比较好想了。

如果有确定没学会的人，相当于给他周围的人（与他吃饭的人）的的下限。
因为他们吃饭的时间一定在，然后就必须大于，即下限为。

（接下来这点自己没想到）
然后这个下限的影响是可以扩散的。
设一个人为，和他吃饭的某人为。
如果，就说明不能给传授算法，那么他们吃饭时不应该会算法。
为保证最小，吃饭时间一定为，则。

这个过程可以用最短路维护。

在此基础上，贪心显然仍成立。
那么接着最短路转移,过程中保证即可。

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<algorithm>
  7. #include<queue>
  8. #define ll long long
  9. #define re register
  10. #define il inline
  11. #define pi pair<int,int>
  12. #define mk make_pair
  13. #define fi first
  14. #define se second
  15. #define fp(i,a,b) for(re int i=a;i<=b;++i)
  16. #define fq(i,a,b) for(re int i=a;i>=b;--i)
  17. using namespace std;
  18. const int M=2e5+100;
  19. int n,m,tar[M],lim[M];
  20. struct dat{int u,v,L,R;}a[M];
  21. bool vis[M];
  22. int h[M],cnt,dis[M];
  23. struct Edge{int to,nxt,mn,mx;}e[M<<1];
  24. il void add(re int u,re int v,re int mn,re int mx)
  25. {
  26.   e[++cnt]=(Edge){v,h[u],mn,mx};h[u]=cnt;
  27.   e[++cnt]=(Edge){u,h[v],mn,mx};h[v]=cnt;
  28. }
  29. il ll gi()
  30. {
  31.   re ll x=0,t=1;
  32.   re char ch=getchar();
  33.   while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  34.   if(ch=='-') t=-1,ch=getchar();
  35.   while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  36.   return x*t;
  37. }
  38. il int min(re int x,re int y){return x<y?x:y;}
  39. il int max(re int x,re int y){return x>y?x:y;}
  40. il void Dijstra()
  41. {
  42.   priority_queue<pi,vector<pi>,greater<pi> >Q;
  43.   while(!Q.empty()) Q.pop();
  44.   fp(i,1,n) vis[i]=0,dis[i]=1e9+7;
  45.   dis[1]=0;Q.push(mk(0,1));
  46.   while(!Q.empty())
  47.     {
  48.       re int u=Q.top().se;Q.pop();
  49.       vis[u]=1;
  50.       for(re int i=h[u];i+1;i=e[i].nxt)
  51.     {
  52.       re int v=e[i].to,mx=e[i].mx,mn=e[i].mn,g=max(max(lim[v],mn),dis[u]);
  53.       if(dis[v]>g&&g<=mx)
  54.         {
  55.           dis[v]=g;
  56.           Q.push(mk(dis[v],v));
  57.         }
  58.     }
  59.       while(!Q.empty()&&vis[Q.top().se]) Q.pop();
  60.     }
  61. }
  62. il void Pre_SPFA()
  63. {
  64.   queue<int>Q;
  65.   while(!Q.empty()) Q.pop();
  66.   fp(i,1,n)
  67.     {
  68.       tar[i]=gi();
  69.       if(tar[i]==-1) lim[i]=1e9+7,vis[i]=1,Q.push(i);
  70.       else vis[i]=0;
  71.     }
  72.   while(!Q.empty())
  73.     {
  74.       re int u=Q.front();Q.pop();
  75.       for(re int i=h[u];i+1;i=e[i].nxt)
  76.     {
  77.       re int v=e[i].to,mn=e[i].mn,mx=e[i].mx;
  78.       if(lim[u]>mx)
  79.       if(lim[v]<mn+1)
  80.         {
  81.           lim[v]=mn+1;
  82.           if(!vis[v]) vis[v]=1,Q.push(v);
  83.         }
  84.     }
  85.       vis[u]=0;
  86.     }
  87. }
  88. int main()
  89. {
  90.   freopen("lunch.in","r",stdin);
  91.   freopen("lunch.out","w",stdout);
  92.   memset(h,-1,sizeof(h));
  93.   n=gi();m=gi();
  94.   fp(i,1,m)
  95.     {
  96.       a[i].u=gi(),a[i].v=gi(),a[i].L=gi(),a[i].R=gi();
  97.       add(a[i].u,a[i].v,a[i].L,a[i].R);
  98.     }
  99.   Pre_SPFA();
  100.   Dijstra();
  101.   fp(i,1,n)
  102.        if(tar[i]==1&&dis[i]>1e9) {puts("Impossible");exit(0);}
  103.   fp(i,1,m)
  104.     {
  105.       if(tar[a[i].u]==-1)
  106.       if(dis[a[i].v]<=a[i].L) {puts("Impossible");exit(0);}
  107.       if(tar[a[i].v]==-1)
  108.       if(dis[a[i].u]<=a[i].L) {puts("Impossible");exit(0);}
  109.     }
  110.   fp(i,1,m)
  111.     {
  112.       re int u=a[i].u,v=a[i].v;
  113.       if(tar[u]==-1||tar[v]==-1) printf("%d\n",a[i].L);
  114.       else printf("%d\n",max(dis[u],dis[v])>a[i].R?a[i].L:max(a[i].L,max(dis[u],dis[v])));
  115.     }
  116.   fclose(stdin);
  117.   fclose(stdout);
  118.   return 0;
  119. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注