题解 P3436 【[POI2006]PRO-Professor Szu】

【POI补全计划#20 POI2006 PRO】 首先为了方便，把“从别墅走到主建筑楼”视为“从主建筑楼走到别墅”，然后把所有边反向（为了方便dfs），这样对题目答案没有影响 接下来记录主建筑能走到那些建筑，把走不到的建筑（和它们的出边）从图中去掉 然后在能走到的建筑中记录每个点的入度（不包含从“走不到的建筑”连向“能走道的建筑”的边），进行拓扑排序 在拓扑排序的过程中记录方案数，如果排到一半发现没有待处理的，入度为0的点时说明剩下的点中存在环，可以有无限种方案走向剩余的点 在记录方案的过程中如果遇到方案数>36500的点则设为一个固定的，略大于36500的数，防止爆int 最后输出一下方案就好了，注意无限种方案和方案数>36500的点都需要输出 贴代码： ```cpp #include<iostream> #include<cstdio> #include<vector> #include<queue> #include<algorithm> using namespace std; const int MAXN=1000010; struct edge { int v; edge *next; }*h[MAXN],pool[MAXN]; int deg[MAXN],top,cnt; inline void addedge(int v,int u) { edge *tmp=&pool[++top];tmp->v=v;tmp->next=h[u];h[u]=tmp;deg[v]++; } int dp[MAXN],vis[MAXN]; vector<int> ans; void dfs(int u) { vis[u]=1;cnt++; for(edge *tmp=h[u];tmp;tmp=tmp->next) { if(!vis[tmp->v])dfs(tmp->v); } } queue<int> q; int main() { int n,m,a,b; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); addedge(a,b); } dfs(n+1); for(int i=1;i<=n;i++) { if(!vis[i]) { for(edge *tmp=h[i];tmp;tmp=tmp->next) { deg[tmp->v]--; } } } q.push(n+1); dp[n+1]=1; while(!q.empty()) { int u=q.front();q.pop(); cnt--;vis[u]=0; for(edge *tmp=h[u];tmp;tmp=tmp->next) { dp[tmp->v]+=dp[u]; deg[tmp->v]--; if(deg[tmp->v]==0) { if(dp[tmp->v]>36500) { dp[tmp->v]=36501; ans.push_back(tmp->v); cnt++; } q.push(tmp->v); } } } if(cnt==0) { int maxx=0; for(int i=1;i<=n;i++) { if(dp[i]>maxx) { maxx=dp[i]; ans.clear(); ans.push_back(i); } else if(dp[i]==maxx)ans.push_back(i); } sort(ans.begin(),ans.end()); printf("%d\n%d\n",maxx,ans.size()); for(auto x:ans)printf("%d ",x); return 0; } for(int i=1;i<=n;i++)if(vis[i])ans.push_back(i); sort(ans.begin(),ans.end()); printf("zawsze\n%d\n",ans.size()); for(auto x:ans)printf("%d ",x); return 0; } ```