1 条题解
-
0
C++ :
#include<iostream> using namespace std; int a[10001][301]={0},into[10001],ans[10001],m,n,money; void init() //读入数据,并构建图,统计入度 { int i,x,y; cin>>n>>m; for(i=1;i<=m;i++) { cin>>x>>y; a[y][0]++; //记录由y引出边的数目 a[y][a[y][0]]=x; //记录由a[y][0]引出边的顶点 into[x]++; //统计入度 } } bool topsort() //拓扑排序 { int t,tot,k,i,j; tot=0;k=0; while(tot<n) //tot顶点个数 { t=0; //用来判断有无环 for(i=1;i<=n;i++) if(into[i]==0) { tot++;t++;money+=100; ans[t]=i; into[i]=0xfffffff; } if(t==0)return false; //存在环 money+=k*t;k++; for(i=1;i<=t;i++) //去掉相连的边 for(j=1;j<=a[ans[i]][0];j++)into[a[ans[i]][j]]--; } return true; } int main() { init();money=0; if(topsort())cout<<money<<endl; else cout<<"Poor Xed"<<endl; return 0; }
- 1
信息
- ID
- 1855
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者