社区讨论
求大佬解答为何全T?
P3243[HNOI2015] 菜肴制作参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mi6z9ngj
- 此快照首次捕获于
- 2025/11/20 13:15 4 个月前
- 此快照最后确认于
- 2025/11/20 13:15 4 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=100001;
int n,m,x,y,head,tail,cnt,sum,top;
int p[N],v[N],h[N],h1[N],num[N],vis[N],que[N*3];
struct Edge{
int to,nxt;
}s[N*2],e[N*2];
struct fuck{
bool operator()(int a,int b)
{
return (num[a]==num[b])? a>b:num[a]>num[b];
}
};
priority_queue<int,vector<int>,fuck >q;
inline void add(int x,int y)
{
cnt++;
s[cnt].to=y;
s[cnt].nxt=h[x];
h[x]=cnt;
e[cnt].to=x;
e[cnt].nxt=h1[y];
h1[y]=cnt;
}
inline int read()
{
int x=0,ff=1;
char c;
c=getchar();
while(c<'0' || c>'9'){ if (c=='-') ff=-1; c=getchar(); }
while(c>='0' && c<='9') { x=x*10+c-48; c=getchar(); }
return x*ff;
}
int main()
{
freopen("fa.in","r",stdin);
freopen("fa.out","w",stdout);
register int T=read();
while(T--)
{
memset(s,0,sizeof(s));
memset(p,0,sizeof(p));
memset(h,0,sizeof(h));
memset(vis,0,sizeof(vis));
memset(num,0,sizeof(num));
memset(que,0,sizeof(que));
memset(v,0,sizeof(v));
memset(h1,0,sizeof(h1));
memset(e,0,sizeof(e));
cnt=0; head=0; tail=0;
n=read(); m=read();
for(register int i=1;i<=m;++i)
{
x=read(); y=read();
add(x,y);
v[x]++; p[y]++;
}
for(register int i=1;i<=n;++i)
if (p[i]==0) q.push(i);
if (q.empty()) { printf("Impossible!\n"); continue; }
for(register int i=1;i<=n;++i)
if (v[i]==0) { que[++tail]=i; vis[i]=1; num[i]=i; }
while(head<tail)
{
head++;
register int d=que[head];
for(register int i=h1[d];i;i=e[i].nxt)
{
register int a=e[i].to;
if (!vis[a]) { vis[a]=1; que[++tail]=a; }
num[a]=(num[a]==0)? min(a,num[d]):min(num[a],min(a,num[d]));
}
}
while(!q.empty())
{
register int k=q.top();
printf("%d ",k);
q.pop();
for(register int i=h[k];i;i=s[i].nxt)
{
register int l=s[i].to;
p[l]--;
if (p[l]==0) q.push(l);
}
}
printf("\n");
}
return 0;
}
反向拓扑一遍求每个点到最后一个点最小的节点编号存在num数组里。全T了QAQ
回复
共 2 条回复,欢迎继续交流。
正在加载回复...