首页 > 代码库 > ZOJ2193 AOV建模
ZOJ2193 AOV建模
每个窗口有四个小区域组成,那么不断往前递推,到达打开当前窗口时必然是那些在上面出现的窗口都已经被打开过了,那么我们可以认为是在第i个窗口的位置上出现了
j , 那么in[i]++ , 只有 i 入度为0时,才说明第i 个窗口上的所有数字对应的窗口已经出现了不用再考虑了,然后建好了AOV网络模型,我们直接判断是否有环就可以了
1 #include <cstdio> 2 #include <cstring> 3 #include <stack> 4 #include <iostream> 5 using namespace std; 6 #define N 1005 7 8 int first[11] , in[11] , num[5][5] , k , vis[10][10]; 9 char s1[N] , s2[N];10 11 struct Node12 {13 int y , next;14 }node[N<<1];15 16 void add_edge(int x,int y)17 {18 in[y]++;19 node[k].y = y , node[k].next = first[x];20 first[x] = k++;21 }22 23 void init()24 {25 memset(vis,0,sizeof(vis));26 for(int i=1 ; i<=9 ;i++) vis[i][i] = 1;27 k = 0;28 for(int i=1 ; i<=9 ; i++){29 int t = i-1;30 int u = t%3 , v = t/3;31 if(!vis[num[v+2][u+1]][i]){32 add_edge(num[v+2][u+1] , i);33 vis[num[v+2][u+1]][i] = 1;34 }35 if(!vis[num[v+1][u+1]][i]){36 add_edge(num[v+1][u+1] , i);37 vis[num[v+1][u+1]][i] = 1;38 }39 if(!vis[num[v+2][u+2]][i]){40 add_edge(num[v+2][u+2] , i);41 vis[num[v+2][u+2]][i] = 1;42 }43 if(!vis[num[v+1][u+2]][i]){44 add_edge(num[v+1][u+2] , i);45 vis[num[v+1][u+2]][i] = 1;46 }47 }48 }49 50 bool dag(int n)51 {52 stack<int> s;53 for(int i = 1 ; i<=n ; i++){54 if(!in[i])55 s.push(i);56 }57 for(int i = 0 ; i<n ; i++){58 if(s.empty()){59 return false;60 }61 int u = s.top();62 s.pop();63 for(int i=first[u] ; i!=-1 ; i=node[i].next){64 int v = node[i].y;65 in[v]--;66 if(!in[v]) s.push(v);67 }68 }69 return true;70 }71 72 int main()73 {74 // freopen("a.in" , "rb" , stdin);75 76 while(~scanf("%s",s1)){77 if(strlen(s1) > 6) break;78 79 memset(first , -1 , sizeof(first));80 memset(in , 0 , sizeof(in));81 82 for(int i=1 ; i<=4 ; i++)83 for(int j=1 ; j<=4 ; j++){84 scanf("%d",&num[i][j]);85 }86 87 init();88 89 if(dag(9)) puts("THESE WINDOWS ARE CLEAN");90 else puts("THESE WINDOWS ARE BROKEN");91 92 scanf("%s",s2);93 }94 return 0;95 }
ZOJ2193 AOV建模
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。