东莞南城网站设计,北京网站制作公司招聘,wordpress 插件出错,哪个网站做试卷吧有答案- 题意 给出我们从1-n城市的点能直接#xff08;或间接#xff09;到达的城市的数量作为这个点的权值 让我们判断并构造一个单向图 使得这个图完全契合给出的数据 special judge 任意一组结果就可以题目中给出 图中无环无回路- 分析
刚看到根据联通数目构造图 哇 这怎么做 好…- 题意 给出我们从1-n城市的点能直接或间接到达的城市的数量作为这个点的权值 让我们判断并构造一个单向图 使得这个图完全契合给出的数据 special judge 任意一组结果就可以题目中给出 图中无环无回路- 分析
刚看到根据联通数目构造图 哇 这怎么做 好复杂啊这该如何构造
其实想一下就可以发现 题目中说是一个无环图 也就是说 任何一个有向无环图中必定至少存在一个入度为0的顶点至少存在一个出度为0的顶点否则图中必存在环。有向无环图对于构造一个任务必须发生在另一个任务之前的这种依赖模型特别有效。有向无环图的另一个应用是规划项目例如建造房屋时框架的设计必须在盖屋顶之前。 否则 如果无环图中的每一个点都有出度的话 这与无环的性质矛盾
我们说 一个无环图就是一个可以被拓补排序的图 也就说 这个图 一定可以被拓扑排序
所以我们发现
低权值的点 不会连向高权值的点 因为一个低权值的点 如果连向一个比自己权值高的点就会产生矛盾 所以当我们把低权值的点处理完后 把每一层低权值的点处理完后 相应的高一层的点就相当于单个点 就像拓扑排序 因为高一层的点来自低一层的点 所以我们从低到高处理 每处理完一层点比其只高一层的点 就相当于单个点 就像是拓扑排序的步骤
每排好一个点 就把这个点的出度全部删除 这里同理
每选完一个点 就把这个点 直接到达的点看成 无入度点 所以就可以一个个选了
生序排序 从低到高处理 相当于反向拓扑排序的步骤 如果这个处理的这个点 找不到足够的点 可以连
就输出NO
证明一个有向图是有向无环图方法 拓扑排序方法code
#includebits/stdc.h
using namespace std;
vectorintv[1010];
struct node{int o,val;
}a[1010];
bool cmp(node aa,node bb){return aa.valbb.val;
}
int main()
{int p,t,n;scanf(%d,t);for( p1;pt;p){scanf(%d,n);for(int i1;in;i){scanf(%d,a[i].val);a[i].o i;}printf(Case #%d: ,p);sort(a1,a1n,cmp);if(a[1].val!0){puts(No);continue;}int i,c0,j;bool f0;for(i1;in;i){if(a[i].val0)continue;for(j1;jija[i].val;j){v[a[i].o].push_back(a[j].o);c;}if(v[a[i].o].size()!a[i].val){f1;break;}}if(f)puts(No);else{puts(Yes);printf(%d\n,c);for(int i1;in;i)for(int j0;jv[i].size();j)printf(%d %d\n,i,v[i][j]);}for(int i1;in;i)v[i].clear();}return 0;
}
