为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
Sgu/122
来自NOCOW
< Sgu
求满足Ore条件的图的哈密尔顿回路.(题目所说的条件强于Ore条件,Ore条件是,对于一个无向图,任意两个互异不相邻的点的度数(去除自环和重边)和不小于点数).算法: (1)随意找到一条路.goto (2). (2)如果这条路的首尾相邻且路长 != n(n为顶点数),goto (a);若首尾相邻且路长==n,输出;否则,先将此路向两侧延伸至无法延伸,goto (3). (a)随便找出一条连接路中顶点和路外顶点的边,把它加入路,并从路中删去一条和新加入的边相邻的边,从而使得路变成一个更长的路. (3)设路径为a-k1-k2-...-km-b,找到路中一个顶点kj,要求满足a和kj相邻且k(j-1)和b相邻.这样删除边k(j-1)-kj,加入边a-kj和k(j-1)-b,从而使得路变成一个首尾相邻的等长的路. 证明:首先,满足Ore条件的图是连通的.设图中有n个点.否则若图不连通,则可以分为两个互不连通部分,分别有s个点和(n-s)个点.我们任取这两个互不连通部分中各一点,它们的度数和最多s-1+n-s-1=n-2<n.这不满足Ore条件.得证. 既然满足Ore条件的图是连通的,(2)算法总可以成功找到这样一条边. 再证明(3).由于这个路是不能再延伸的,所以路的头尾两点发出的边都指向路中的点,且这两个点的度数和>=n(这两个点一定不相邻,见(2)).(3)中可能成为j的下标有2...m这m-1个,由于m-1<n,由抽屉原理,总存在满足条件的j. 这样整个算法就能正确的执行.每次(3)开始之前都一定要延伸路径,强烈提示注意.
//P*M #include<cstdio> #include<cstring> char ch1; bool map[1001][1001], f[1001], flag; int hd, tl, p, n, x, found, p1, cl, q[1001], suc[1001]; int main(){ freopen("sgu122.in", "r", stdin); freopen("sgu122.out", "w", stdout); scanf("%d", &n); memset(map, false, sizeof(map)); for(int i = 1; i <= n; i++){ scanf("%d", &x); map[i][x] = true; map[x][i] = true; scanf("%c", &ch1); while(ch1 != '\n' && !feof(stdin)){scanf("%d", &x); map[i][x] = true; map[x][i] = true; scanf("%c", &ch1);} } hd = 1; tl = 1; memset(suc, 0, sizeof(suc)); found = 1; memset(f, true, sizeof(f)); f[1] = false; flag = true; while(flag){ flag = false; for(int i = 1; i <= n; i++){ if(map[tl][i] && f[i]){flag = true; suc[tl] = i; tl = i; f[i] = false; found++; break;} } } flag = true; while(flag){ flag = false; for(int i = 1; i <= n; i++){ if(map[hd][i] && f[i]){flag = true; suc[i] = hd; hd = i; f[i] = false; found++; break;} } } while(true){ if(map[hd][tl] == true){ if(found == n){ suc[tl] = hd; printf("1 "); p = 1; for(int i = 1; i <= n; i++){ printf("%d ", p = suc[p]); } printf("\n"); break; }else{ p = hd; while(true){ flag = false; for(int i = 1; i <= n; i++){ if(f[i] && map[p][i]){ suc[tl] = hd; hd = suc[p]; suc[p] = i; tl = i; f[i] = false; ++found; flag = true; break; } } if(flag){break;} p = suc[p]; } flag = true; while(flag){ flag = false; for(int i = 1; i <= n; i++){ if(map[tl][i] && f[i]){flag = true; suc[tl] = i; tl = i; f[i] = false; found++; break;} } } flag = true; while(flag){ flag = false; for(int i = 1; i <= n; i++){ if(map[hd][i] && f[i]){flag = true; suc[i] = hd; hd = i; f[i] = false; found++; break;} } } } }else{ p = hd; while(true){ if(map[hd][suc[p]] && map[tl][p]){ break; } p = suc[p]; } p1 = suc[p]; cl = 0; while(p1 != tl){q[++cl] = p1; p1 = suc[p1];} for(int i = cl; i >= 1; i--){ suc[suc[q[i]]] = q[i]; } suc[suc[p]] = 1; suc[p] = tl; tl = q[1]; } } fclose(stdin); fclose(stdout); return 0; }
/by Logic #include<stdio.h> #include<algorithm> using namespace std; const int maxn=1050; int n,st,en,l; bool bel[maxn]={0}; int co[maxn]={0}; bool e[maxn][maxn]={0}; int pr[maxn],ne[maxn]; bool add(int x,bool su) { int i,j; for(i=1;i<=n;i++) if(e[x][i]&&!bel[i]) { for(j=1;j<=n;j++) if(e[i][j]) co[j]=i; if(!su) ne[i]=x,pr[x]=i,st=i; else ne[x]=i,pr[i]=x,en=i; bel[i]=1; l++; return 1; } return 0; } int main() { #ifndef ONLINE_JUDGE freopen("data.in","r",stdin); #endif int i,j,t; char ci; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&t); if(i==1) en=t; e[i][t]=1; ci=getchar(); while(ci!='\n'&&ci!='\r'&&ci!=EOF) scanf("%d",&t),e[i][t]=1,ci=getchar(); } st=1,l=2; bel[st]=bel[en]=1; ne[st]=en,pr[en]=st; while(1) { while(add(st,0)); while(add(en,1)); if(e[st][en]) { if(l==n) {ne[en]=st,pr[st]=en;break;} for(i=1;i<=n;i++) if(!bel[i]&&co[i]) { ne[en]=st,pr[st]=en; st=i,en=pr[co[i]]; ne[st]=co[i],pr[co[i]]=st; bel[i]=1,l++; break; } } else for(i=ne[st];ne[i]!=en;i=ne[i]) { if(e[i][en]&&e[st][ne[i]]) { for(j=en;j!=i;j=ne[j]) swap(pr[j],ne[j]); t=ne[i]; ne[i]=en,pr[en]=i; en=t; break; } } } for(i=1;i!=pr[1];i=ne[i]) printf("%d ",i); printf("%d %d\n",pr[1],1); return 0; }
