首页 > 代码库 > hdu4948 Kingdom
hdu4948 Kingdom
题意:有n个城市,任意两点之间有且仅有一条有向边。要求输出一种建造城市的顺序,使得之前已经建造的城市可以到达当前建造的城市,且至多经过两条边。
首先我们可以证明,这种方案是肯定存在的,
因为在一个满足题意的图中,入度最大的点一定是其他点在两步之内可达的。那么这个点就最后输出。
上面的结论是为什么呢。。题解告诉我们用反证法证明,
若u结点是当前图中入度最大的结点,假设v点存在该路径v->a->b->u,
由于u是入度最大的结点,那么v 不可能连到u以及 b或者与u直接相连的点(不然v就可以两步到达u了),
由于两点间有一条有向边,v连布到他们,那么他们到v一定有边,既v的入度至少是 u+指向u的点,既v的入度大于u的,这里矛盾了。
所以我们可以知道,在任何一个符合题意的图中,都可以知道最后输出的点,
我们每找到一个点,就标记,把与该点相连的边删去。这样找完了倒序输出就i可以了。
#include <iostream> #include <cstdlib> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <map> #define inf 0x3f3f3f3f #pragma comment(linker, "/STACK:16777216") #define eps 1e-6 #define ll long long using namespace std; const int maxn=505; int n,in[maxn],vis[maxn]; char s[maxn][maxn]; int main() { int i,j; while(~scanf("%d",&n)&&n) { memset(in,0,sizeof in); for(i=1;i<=n;i++) { scanf("%s",s[i]+1); for(j=1;j<=n;j++) if(s[i][j]=='1') in[j]++; } vector<int> ans; memset(vis,0,sizeof vis); int maxin,p,flag=1; while(flag) { flag=0,maxin=-1,p=0; for(i=1;i<=n;i++) { if(!vis[i]&&maxin<in[i]) { flag=1; maxin=in[i]; p=i; } } if(flag) { vis[p]=1; ans.push_back(p); for(i=1;i<=n;i++) { if(i==p) continue; if(s[p][i]=='1') in[i]--; } } } printf("%d",ans[ans.size()-1]); for(i=ans.size()-2;i>=0;i--) printf(" %d",ans[i]); puts(""); } return 0; } /* 4 0111 0011 0001 0000 4 0100 0010 1001 1100 1 2 3 4 3 4 1 2 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。