2046. 愚者指名自己的辩护人

2046. 愚者指名自己的辩护人 

输入

第一行两个整数 N,M，表示点数和边数。
接下来一行 N 个整数，第 i 个正整数表示 Pi。
接下来 M 行，每行两个整数 u,v，表示有一条无向边连接了 u 和 v。

输出

输出 N 行，每行为一个 0 或 1，意义如题目描述所示。

样例输入

7 8
1 50 49 10 90 90 1
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
 

样例输出

1
0
1
1
0
0
1

思想就是弗洛伊德，然后去掉一个点弗洛伊德，对结果没影响就不是一定要经过的。

constmaxn=200;
vara,b,c:array[0..maxn,0..maxn] of extended;f:array[0..maxn]of extended;ans:array[0..maxn] of longint;i,j,k,l,n,m:longint;min:extended;beginassign(input,'fool.in');reset(input);assign(output,'fool.out');rewrite(output);readln(n,m);fori:=1 to n dobeginread(f[i]);f[i]:=100-f[i];end;readln;fork:=1 to m dobeginreadln(i,j);a[i,j]:=f[j];a[j,i]:=f[i];end;b:=a;c:=a;fork:=1 to n dofori:=1 to n dofor j:=1 to n doif (i<>J) and (i<>k) and (j<>k) thenif b[i,j]<b[i,k]*b[k,j]/100 thenb[i,j]:=b[i,k]*b[k,j]/100;min:=b[1,n];ans[1]:=1;forl:=1 to n dobeginc:=a;for k:=1 to n dofor i:=1 to n dofor j:=1 to n doif (l<>i) and (l<>j) and (l<>k) thenif (i<>j) and (i<>k) and(j<>k) thenif c[i,j]<c[i,k]*c[k,j]/100 thenc[i,j]:=c[i,k]*c[k,j]/100;if (abs(min-c[1,n])>0.0000000000000001) or (c[1,n]=0) then ans[l]:=1;end;ans[n]:=1;fori:=1 to n dowriteln(ans[i]);close(input);close(output);
end.