[破碎的状态] [-11] USACO 1.3 Wormholes
题意在这里:
http://www.nocow.cn/index.php/Translate:USACO/wormhole
实际上我只是练一发拓扑排序..
/* ID: absi2011 PROG: wormhole LANG: C++ */ #include<set> #include<map> #include<list> #include<queue> #include<stack> #include<string> #include<time.h> #include<math.h> #include<memory> #include<vector> #include<bitset> #include<fstream> #include<stdio.h> #include<utility> #include<sstream> #include<string.h> #include<iostream> #include<stdlib.h> #include<algorithm> using namespace std; int next[25]; int x[25],y[25]; int ans=0; int visit[25]; int n; int in[25]; void topo_sort() { int i; int m=n*2; for (i=0;i<m;i++) { in[i]=0; } for (i=0;i<m;i++) { if (next[i]!=-2) in[next[i]]++; } static int que[105]; int front=0,rail=0; for (i=0;i<m;i++) { if (in[i]==0) { que[rail++]=i; } } for (;front<rail;front++) { int t=que[front]; if (next[t]==-2) continue; in[next[t]]--; if (in[next[t]]==0) { que[rail++]=next[t]; } } if (rail!=m) ans++; } void dfs(int x) { if (x>=n) { topo_sort(); return; } if (visit[x]) { dfs(x+1); return; } int i; visit[x]=true; for (i=x+1;i<n;i++) { if (visit[i]) continue; next[i*2]=x*2+1; next[x*2]=i*2+1; visit[i]=true; dfs(x+1); visit[i]=false; } visit[x]=false; } int main() { freopen("wormhole.in","r",stdin); freopen("wormhole.out","w",stdout); scanf("%d",&n); int i; for (i=0;i<n;i++) { scanf("%d%d",&x[i],&y[i]); } for (i=0;i<n;i++) { int j; int t=-1; for (j=0;j<n;j++) { if (y[i]==y[j]) { if (x[j]<=x[i]) continue; if ((t==-1)||(x[j]<=x[t])) { t=j; } } } next[i*2+1]=t*2; } dfs(0); printf("%d\n",ans); return 0; }