不知道为嘛被分在ＤＰ里了 瞎写 注意没被别的轮带动的情况 初始为０ 分母为１
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<queue> 8 using namespace std; 9 #define N 1010 10 vector<int>ge[N]; 11 int co[N],d[N],vis[N]; 12 struct node 13 { 14 int f,nu,de; 15 }p[N]; 16 int gcd(int a,int b) 17 { 18 return b==0?a:gcd(b,a%b); 19 } 20 void init(int x,int y) 21 { 22 int n1 = co[x]*p[x].nu,n2 = co[y]*p[x].de; 23 if(n1==0||n2==0) n2=1; 24 else 25 { 26 int k = gcd(n1,n2); 27 n1 = n1/k;n2 = n2/k; 28 } 29 if(d[y]==1) 30 p[y].f = 1; 31 else 32 p[y].f = -1; 33 p[y].nu = n1; 34 p[y].de = n2; 35 } 36 void bfs(int u) 37 { 38 queue<int>q; 39 q.push(u); 40 while(!q.empty()) 41 { 42 int tu = q.front(); 43 q.pop(); 44 for(int i = 0 ; i < (int)ge[tu].size() ; i++) 45 { 46 int v = ge[tu][i]; 47 if(!vis[v]) 48 { 49 vis[v] = 1; 50 d[v] = -d[tu]; 51 init(tu,v); 52 q.push(v); 53 } 54 } 55 } 56 } 57 int main() 58 { 59 int i,n,s,v; 60 scanf("%d",&n); 61 for(i = 1; i <= n ; i++) 62 { 63 scanf("%d",&co[i]); 64 int a; 65 while(scanf("%d",&a)&&a) 66 ge[i].push_back(a); 67 } 68 scanf("%d%d",&s,&v); 69 d[s] = 1; 70 p[s].f = 1; 71 p[s].nu = v; 72 p[s].de = 1; 73 vis[s] = 1; 74 bfs(s); 75 for(i = 1; i <= n ; i++) 76 { 77 if(p[i].f==-1&&p[i].nu) 78 printf("-"); 79 if(p[i].nu==0) 80 p[i].de = 1; 81 printf("%d/%d ",p[i].nu,p[i].de); 82 } 83 return 0; 84 }