题意:给出 n 个点,m 条有向边,有的点的点权已知,其余的未知,点权都在 1-k 中。先希望你确定出所有点的点权,满足:
对于所有边 a->b,a 的点权 > b 的点权
对于 i=1..k,至少有一个点的点权为 i
n,m,k<=100000
题解:像菜肴制作一样奇怪的拓扑排序题,直接上方法吧,不会证。
先正反跑两边拓扑排序,得出每个点点权的下界 Li 和上界 Ri。
将所有点按上界从小到大排序,然后枚举权值 i。将所有上界为 i 的点都扔到堆中,再从堆里取出下界最大的那个点,将其权值赋为 i。再找出所有下界为 i 的点,将他们的权值也都赋为 i 即可。
- #include <cstdio>
- #include <cstring>
- #include <utility>
- #include <queue>
- #include <vector>
- #define mp(A,B) make_pair(A,B)
- using namespace std;
- const int maxn=200010;
- typedef pair<int,int> pii;
- int n,m,k,cnt,flag;
- int to[maxn],nxt[maxn],head[maxn],pa[maxn],pb[maxn],v[maxn],L[maxn],R[maxn],d[maxn],ans[maxn];
- vector<int> p[maxn];
- vector<int>::iterator it;
- queue<int> q;
- priority_queue<pii> pq;
- inline int rd()
- {
- int ret=0,f=1; char gc=getchar();
- while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
- while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar();
- return ret*f;
- }
- inline void add(int a,int b)
- {
- to[cnt]=b,nxt[cnt]=head[a],head[a]=cnt++;
- }
- int main()
- {
- n=rd(),m=rd(),k=rd();
- int i,u;
- for(i=1;i<=n;i++)
- {
- v[i]=rd();
- if(!v[i]) L[i]=1,R[i]=k;
- else L[i]=R[i]=v[i];
- }
- memset(head,-1,sizeof(head)),cnt=0;
- for(i=1;i<=m;i++) pa[i]=rd(),pb[i]=rd(),d[pb[i]]++,add(pa[i],pb[i]);
- for(i=1;i<=n;i++) if(!d[i]) q.push(i);
- while(!q.empty())
- {
- u=q.front(),q.pop();
- for(i=head[u];i!=-1;i=nxt[i])
- {
- d[to[i]]--,R[to[i]]=min(R[to[i]],R[u]-1);
- if(!d[to[i]]) q.push(to[i]);
- }
- }
- for(i=1;i<=n;i++) if(d[i]) return puts("-1"),0;
- memset(head,-1,sizeof(head)),cnt=0;
- for(i=1;i<=m;i++) d[pa[i]]++,add(pb[i],pa[i]);
- for(i=1;i<=n;i++) if(!d[i]) q.push(i);
- while(!q.empty())
- {
- u=q.front(),q.pop();
- for(i=head[u];i!=-1;i=nxt[i])
- {
- d[to[i]]--,L[to[i]]=max(L[to[i]],L[u]+1);
- if(!d[to[i]]) q.push(to[i]);
- }
- }
- for(i=1;i<=n;i++) if(d[i]||L[i]>R[i]) return puts("-1"),0;
- for(i=1;i<=n;i++) p[R[i]].push_back(i);
- for(i=k;i>=1;i--)
- {
- for(it=p[i].begin();it!=p[i].end();it++) pq.push(mp(L[*it],*it));
- if(pq.empty()) return puts("-1"),0;
- u=pq.top().second,pq.pop(),ans[u]=i;
- while(!pq.empty())
- {
- u=pq.top().second;
- if(L[u]<i) break;
- pq.pop(),ans[u]=i;
- }
- }
- for(i=1;i<=n;i++) printf("%d ",ans[i]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2438766.html